Suponiendo que puede usar cada número en la matriz solo una vez, este es un problema de suma de subconjuntos , que es una instancia del problema de la mochila. El problema de la mochila es NP-hard, por lo que no hay algoritmos que puedan resolver esto de manera eficiente para cualquier instancia de problema, pero el enlace de Wikipedia ofrece punteros sobre los enfoques que puede probar.
En el problema de la mochila completa, todos sus artículos tienen un peso y un valor ; El problema es encontrar el valor máximo que no exceda un peso específico. En el problema de la suma de subconjuntos, el peso y el valor son iguales: solo desea llenar su mochila lo más llena posible.
Al establecer el peso y el valor igual a los números en su matriz, y el peso máximo a 20, encontrará el número más grande menor que 20. Para encontrar el número más pequeño mayor que 20, comience colocando todos los objetos en el mochila, y retire tantos como pueda sin dejar que el peso caiga por debajo de 20; esto se logra estableciendo los pesos y valores como antes, pero estableciendo el peso máximo en la suma de los números menos 20, e interpretando la solución como una especificación de qué elementos se eliminan de la mochila.
- ¿Qué debe aprender primero, algoritmos y DS o un lenguaje de programación?
- ¿Por qué está completo el problema de la mochila NP incluso cuando tiene complejidad O (nW)?
- ¿Cuáles son las aplicaciones de las tablas hash?
- ¿Cómo implementaría el ranking de respuestas de Quora?
- ¿Cuáles son las ventajas y desventajas de los algoritmos y la heurística en la resolución de problemas?
