Solución:
Este problema se puede resolver con combinaciones recursivas de todas las sumas posibles filtrando aquellas que alcanzan el objetivo. Aquí está el algoritmo en Python:
def subset_sum(numbers, target, partial=[]):
s = sum(partial)
# check if the partial sum is equals to target
if s == target:
print "sum(%s)=%s" % (partial, target)
if s >= target:
return # if we reach the number why bother to continue
for i in range(len(numbers)):
n = numbers[i]
remaining = numbers[i+1:]
subset_sum(remaining, target, partial + [n])
if __name__ == "__main__":
subset_sum([3,9,8,4,5,7,10],15)
#Outputs:
#sum([3, 8, 4])=15
#sum([3, 5, 7])=15
#sum([8, 7])=15
#sum([5, 10])=15
Este tipo de algoritmos se explican muy bien en la siguiente conferencia de Programación abstracta de Standford; este video es muy recomendable para comprender cómo funciona la recursividad para generar permutaciones de soluciones.
Editar
Lo anterior como función generadora, lo que lo hace un poco más útil. Requiere Python 3.3+ debido a yield from.
def subset_sum(numbers, target, partial=[], partial_sum=0):
if partial_sum == target:
yield partial
if partial_sum >= target:
return
for i, n in enumerate(numbers):
remaining = numbers[i + 1:]
yield from subset_sum(remaining, target, partial + [n], partial_sum + n)
Aquí está la versión de Java del mismo algoritmo:
package tmp;
import java.util.ArrayList;
import java.util.Arrays;
class SumSet {
static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
int s = 0;
for (int x: partial) s += x;
if (s == target)
System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
if (s >= target)
return;
for(int i=0;i<numbers.size();i++) {
ArrayList<Integer> remaining = new ArrayList<Integer>();
int n = numbers.get(i);
for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
partial_rec.add(n);
sum_up_recursive(remaining,target,partial_rec);
}
}
static void sum_up(ArrayList<Integer> numbers, int target) {
sum_up_recursive(numbers,target,new ArrayList<Integer>());
}
public static void main(String args[]) {
Integer[] numbers = {3,9,8,4,5,7,10};
int target = 15;
sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
}
}
Es exactamente la misma heurística. Mi Java está un poco oxidado, pero creo que es fácil de entender.
Conversión C # de la solución Java: (por @JeremyThompson)
public static void Main(string[] args)
{
List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
int target = 15;
sum_up(numbers, target);
}
private static void sum_up(List<int> numbers, int target)
{
sum_up_recursive(numbers, target, new List<int>());
}
private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
int s = 0;
foreach (int x in partial) s += x;
if (s == target)
Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);
if (s >= target)
return;
for (int i = 0; i < numbers.Count; i++)
{
List<int> remaining = new List<int>();
int n = numbers[i];
for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);
List<int> partial_rec = new List<int>(partial);
partial_rec.Add(n);
sum_up_recursive(remaining, target, partial_rec);
}
}
Solución de rubí: (por @emaillenin)
def subset_sum(numbers, target, partial=[])
s = partial.inject 0, :+
# check if the partial sum is equals to target
puts "sum(#{partial})=#{target}" if s == target
return if s >= target # if we reach the number why bother to continue
(0..(numbers.length - 1)).each do |i|
n = numbers[i]
remaining = numbers.drop(i+1)
subset_sum(remaining, target, partial + [n])
end
end
subset_sum([3,9,8,4,5,7,10],15)
Editar: discusión sobre la complejidad
Como otros mencionan, este es un problema NP-difícil. Se puede resolver en tiempo exponencial O (2 ^ n), por ejemplo, para n = 10 habrá 1024 soluciones posibles. Si los objetivos que está intentando alcanzar están en un rango bajo, este algoritmo funciona. Entonces, por ejemplo:
subset_sum([1,2,3,4,5,6,7,8,9,10],100000) genera 1024 ramas porque el objetivo nunca llega a filtrar posibles soluciones.
Por otra parte subset_sum([1,2,3,4,5,6,7,8,9,10],10) genera solo 175 sucursales, porque el objetivo a alcanzar 10 consigue filtrar muchas combinaciones.
Si N y Target son números grandes, uno debería pasar a una versión aproximada de la solución.
La solución de este problema se ha dado un millón de veces en Internet. El problema se llama El problema del cambio de moneda. Se pueden encontrar soluciones en http://rosettacode.org/wiki/Count_the_coins y un modelo matemático en http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf (o Google problema de cambio de moneda).
Por cierto, la solución Scala de Tsagadai, es interesante. Este ejemplo produce 1 o 0. Como efecto secundario, enumera en la consola todas las posibles soluciones. Muestra la solución, pero falla al hacerla utilizable de alguna manera.
Para ser lo más útil posible, el código debe devolver un List[List[Int]]para permitir obtener el número de solución (longitud de la lista de listas), la “mejor” solución (la lista más corta), o todas las soluciones posibles.
Aquí hay un ejemplo. Es muy ineficiente, pero es fácil de entender.
object Sum extends App {
def sumCombinations(total: Int, numbers: List[Int]): List[List[Int]] = {
def add(x: (Int, List[List[Int]]), y: (Int, List[List[Int]])): (Int, List[List[Int]]) = {
(x._1 + y._1, x._2 ::: y._2)
}
def sumCombinations(resultAcc: List[List[Int]], sumAcc: List[Int], total: Int, numbers: List[Int]): (Int, List[List[Int]]) = {
if (numbers.isEmpty || total < 0) {
(0, resultAcc)
} else if (total == 0) {
(1, sumAcc :: resultAcc)
} else {
add(sumCombinations(resultAcc, sumAcc, total, numbers.tail), sumCombinations(resultAcc, numbers.head :: sumAcc, total - numbers.head, numbers))
}
}
sumCombinations(Nil, Nil, total, numbers.sortWith(_ > _))._2
}
println(sumCombinations(15, List(1, 2, 5, 10)) mkString "n")
}
Cuando se ejecuta, muestra:
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 2, 2, 2, 2, 2)
List(1, 1, 1, 2, 2, 2, 2, 2, 2)
List(1, 2, 2, 2, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5)
List(1, 1, 1, 1, 1, 1, 1, 1, 2, 5)
List(1, 1, 1, 1, 1, 1, 2, 2, 5)
List(1, 1, 1, 1, 2, 2, 2, 5)
List(1, 1, 2, 2, 2, 2, 5)
List(2, 2, 2, 2, 2, 5)
List(1, 1, 1, 1, 1, 5, 5)
List(1, 1, 1, 2, 5, 5)
List(1, 2, 2, 5, 5)
List(5, 5, 5)
List(1, 1, 1, 1, 1, 10)
List(1, 1, 1, 2, 10)
List(1, 2, 2, 10)
List(5, 10)
los sumCombinations() La función se puede usar por sí misma y el resultado se puede analizar más a fondo para mostrar la “mejor” solución (la lista más corta) o el número de soluciones (el número de listas).
Tenga en cuenta que incluso así, es posible que los requisitos no se cumplan por completo. Puede suceder que el orden de cada lista en la solución sea significativo. En tal caso, cada lista tendría que ser duplicada tantas veces como combinación de sus elementos haya. O podríamos estar interesados solo en las combinaciones que son diferentes.
Por ejemplo, podríamos considerar que List(5, 10) debería dar dos combinaciones: List(5, 10) y List(10, 5). Para List(5, 5, 5) podría dar tres combinaciones o una sola, según los requisitos. Para los números enteros, las tres permutaciones son equivalentes, pero si se trata de monedas, como en el “problema del cambio de monedas”, no lo son.
Tampoco se establece en los requisitos la cuestión de si cada número (o moneda) puede usarse solo una o muchas veces. Podríamos (¡y deberíamos!) Generalizar el problema a una lista de listas de apariciones de cada número. Esto se traduce en la vida real en “cuáles son las posibles formas de ganar una cierta cantidad de dinero con un conjunto de monedas (y no un conjunto de valores de monedas)”. El problema original es solo un caso particular de este, donde tenemos tantas ocurrencias de cada moneda como sea necesario para hacer la cantidad total con cada valor de moneda.
En Haskell:
filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]
Y J:
(]#~12345=+/@>)(]<@#~[:#:@i.2^#)1 5 22 15 0 ...
Como puede notar, ambos adoptan el mismo enfoque y dividen el problema en dos partes: genere cada miembro del conjunto de poder y verifique la suma de cada miembro al objetivo.
Hay otras soluciones, pero esta es la más sencilla.
¿Necesita ayuda con alguno de ellos o para encontrar un enfoque diferente?