Interesantes respuestas. 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 mejor respuesta) 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 utiliza la recursividad (naturalmente) también he cambiado de opinión acerca de la firma del método y se fue para la lista> en lugar de decimales [] [] 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 una aplicación para probar esto funciona, prueba este código de la aplicación de 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 alguien más tiene la respuesta más rápidamente (ya sea para hacer la tarea o de otra manera).
Saludos ...
Una solución recursiva sería 1/3 de la longitud y 3 veces más elegante. – Haoest
Es una solución recursiva. Me interesaría ver tu solución de 1/3 de longitud. ¿Tal vez debería examinar la solución antes de comentar? –
Las coincidencias exactas son la coincidencia más cercana. Si la coincidencia más cercana no es la coincidencia exacta, entonces no hay una coincidencia exacta. – wnoise