c# - resueltos - Algoritmo para encontrar qué números de una lista de tamaño n suma a otro número

libro de ejercicios resueltos en c#

Question

Tengo un número decimal (llamémoslo gol ) y una matriz de otros números decimales (llamemos a los elementos de la matriz) y necesito encontrar todas las combinaciones de números de elementos que sumen al objetivo.

Tengo una preferencia por una solución en C # (.Net 2.0) pero puede que el mejor algoritmo gane independientemente.

La firma de su método puede ser algo así como:

public decimal[][] Solve(decimal goal, decimal[] elements)

Answer 1

Creo que tienes un problema de empaque en las manos (que es NP-hard), así que creo que la única solución será probar todas las combinaciones posibles hasta que encuentres una que funcione.

Editar: Como se señala en un comentario, no siempre tendrá que probar cada combinación para cada conjunto de números que encuentre. Sin embargo, cualquier método que se te ocurra tiene el peor conjunto de escenarios de casos donde tendrás que probar cada combinación, o al menos un subconjunto de combinaciones que crece exponencialmente con el tamaño del conjunto.

De lo contrario, no sería NP-difícil.

Answer 2

El problema de suma de subconjuntos y el problema de mochila un poco más general se resuelven con programación dinámica: no se requiere la enumeración de fuerza bruta de todas las combinaciones. Consulte Wikipedia o su referencia de algoritmos favoritos.

Aunque los problemas son NP-completos, son NP-completos muy "fáciles". La complejidad algorítmica en la cantidad de elementos es baja.

Answer 3

Respuestas interesantes Gracias por los consejos para la wikipedia, aunque interesantes, en realidad no resuelven el problema, ya que estaba buscando coincidencias exactas, más un problema de borrado contable / libro que un problema tradicional de bin-packing / knapsack.

He estado siguiendo el desarrollo del desbordamiento de pila con interés y me he preguntado qué tan útil sería. Este problema surgió en el trabajo y me pregunté si el desbordamiento de la pila podría proporcionar una respuesta preparada (o una respuesta mejor) más rápido de lo que podría escribirlo yo mismo. Gracias también por los comentarios que sugieren que se etiquete la tarea. Supongo que es bastante precisa a la luz de lo anterior.

Para aquellos que están interesados, aquí está mi solución que usa la recursión (naturalmente). También cambié mi opinión sobre la firma del método y opté por List> en lugar de decimal [] [] como el tipo de retorno:

public class Solver {
private List<List<decimal>> mResults;
public List<List<decimal>> Solve(decimal goal, decimal[] elements) {
mResults = new List<List<decimal>>();
RecursiveSolve(goal, 0.0m,
new List<decimal>(), new List<decimal>(elements), 0);
return mResults;
}
private void RecursiveSolve(decimal goal, decimal currentSum,
List<decimal> included, List<decimal> notIncluded, int startIndex) {
for (int index = startIndex; index < notIncluded.Count; index++) {
decimal nextValue = notIncluded[index];
if (currentSum + nextValue == goal) {
List<decimal> newResult = new List<decimal>(included);
newResult.Add(nextValue);
mResults.Add(newResult);
}
else if (currentSum + nextValue < goal) {
List<decimal> nextIncluded = new List<decimal>(included);
nextIncluded.Add(nextValue);
List<decimal> nextNotIncluded = new List<decimal>(notIncluded);
nextNotIncluded.Remove(nextValue);
RecursiveSolve(goal, currentSum + nextValue,
nextIncluded, nextNotIncluded, startIndex++);
}
}
}
}

Si quieres que una aplicación pruebe que esto funciona, prueba con este código de la aplicación de la consola:

class Program {
static void Main(string[] args) {
string input;
decimal goal;
decimal element;
do {
Console.WriteLine("Please enter the goal:");
input = Console.ReadLine();
}
while (!decimal.TryParse(input, out goal));
Console.WriteLine("Please enter the elements (separated by spaces)");
input = Console.ReadLine();
string[] elementsText = input.Split('' '');
List<decimal> elementsList = new List<decimal>();
foreach (string elementText in elementsText) {
if (decimal.TryParse(elementText, out element)) {
elementsList.Add(element);
}
}
Solver solver = new Solver();
List<List<decimal>> results = solver.Solve(goal, elementsList.ToArray());
foreach(List<decimal> result in results) {
foreach (decimal value in result) {
Console.Write("{0}/t", value);
}
Console.WriteLine();
}
Console.ReadLine();
}
}

Espero que esto ayude a otra persona a obtener su respuesta más rápidamente (ya sea para tareas o de otra manera).

Aclamaciones...

Answer 4

Si bien no resuelve el problema de la fuerza bruta (como ya se mencionó), primero debes ordenar tus números y luego revisar los posibles (una vez que pasaste el valor de Suma, no puedes agregar ningún número mayor que el Objetivo - Suma).

Esto cambiará la forma en que implemente su algoritmo (para ordenar solo una vez y luego omitir los elementos marcados), pero en promedio mejoraría el rendimiento.

Answer 5

Usted ha descrito un problema de mochila , la única solución verdadera es la fuerza bruta. Hay algunas soluciones de aproximación que son más rápidas, pero pueden no ajustarse a sus necesidades.

Answer 6

public class Logic1 {
static int val = 121;
public static void main(String[] args)
{
f(new int[] {1,4,5,17,16,100,100}, 0, 0, "{");
}
static void f(int[] numbers, int index, int sum, String output)
{
System.out.println(output + " } = " + sum);
//System.out.println("Index value1 is "+index);
check (sum);
if (index == numbers.length)
{
System.out.println(output + " } = " + sum);
return;
}
// include numbers[index]
f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]);
check (sum);
//System.out.println("Index value2 is "+index);
// exclude numbers[index]
f(numbers, index + 1, sum, output);
check (sum);
}
static void check (int sum1)
{
if (sum1 == val)
System.exit(0);
}
}