Cómo resolver el problema de la suma de subconjuntos más cercana en Java para matrices de 100 o más elementos?
Recientemente me encontré con un problema de suma de subconjuntos. Antes pude resolverlo para arreglos más pequeños utilizando Java, pero en este caso realmente no tengo idea de qué hacer. La fuerza bruta y la recursividad probablemente no sean una opción, ya que me encontré con un problema de falta de memoria.
Entonces, digamos que tenemos un arreglo de {2500, 3200, 3300}. Estamos buscando la suma más cercana al número deseado K = 135000. La diferencia principal es que podemos usar los números del arreglo múltiples veces.
Vale, si podemos usarlos múltiples veces, entonces podemos cambiarlo a una manera más “tradicional” – simplemente dividir K por cada uno de estos números – eso es 54, 42 y 40 – y crear un nuevo arreglo, que tenga esos números la cantidad de veces obtenida de la división. Sería {2500, 2500, 2500, …, …, 3300, 3300} y el nuevo arreglo tendría una longitud de 136. Ahora esto es mucho más que 3.
Entonces, ¿cómo resolver el problema de suma de subconjuntos más cercana, donde podemos seleccionar más de 2 números del arreglo de 136 elementos o más usando Java?
Lo que quiero obtener no es solo la suma más cercana, sino también una lista de elementos que dieron esa suma.
Escuché y estuve leyendo sobre programación dinámica, algoritmos de aproximación y algoritmos genéticos, pero desafortunadamente no tengo idea acerca de ellos. Hice un algoritmo genético para un caso diferente hace algún tiempo, pero no estoy seguro de cómo usarlo en este caso.
¿Alguna idea? Estaré realmente agradecido por la ayuda.
davy.ai
Como experto en TI especializado en Java, algoritmos y problemas np-completos, hay diferentes formas en las que puedes abordar el problema de la suma de subconjuntos. Aquí tienes algunas sugerencias:
Algoritmos de aproximación: Otro enfoque es utilizar algoritmos de aproximación. Los algoritmos de aproximación proporcionan una forma de obtener una solución casi óptima en un tiempo razonable. Uno de estos algoritmos es el algoritmo codicioso, que consiste en seleccionar el número más grande posible del arreglo hasta que se alcance o se supere la suma objetivo. Este algoritmo no siempre dará la solución óptima, pero puede proporcionar una buena aproximación.
Algoritmos genéticos: Mencionaste que tienes cierta familiaridad con los algoritmos genéticos. Los algoritmos genéticos involucran la creación de una población de soluciones y el uso de los principios de la selección natural para evolucionar mejores soluciones con el tiempo. Puedes crear una población de posibles soluciones seleccionando números al azar del arreglo y calculando su suma. Luego puedes utilizar operadores genéticos como la mutación y el cruzamiento para generar nuevas soluciones y refinar gradualmente la población hasta encontrar la solución que mejor se ajuste a los criterios deseados.
En resumen, existen múltiples formas de abordar el problema de la suma de subconjuntos. Comprender las ventajas y limitaciones de cada enfoque puede ayudarte a seleccionar el más adecuado según tu situación específica.