Resolviendo el problema NP-completo en XKCD
https://stackoverflow.com/questions/141779
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
El problema / cómic en cuestión: http://xkcd.com/287/
No estoy seguro de que esta sea la mejor manera de hacerlo, pero esto es lo que he encontrado hasta ahora. Estoy usando CFML, pero cualquiera debería poder leerlo.
<cffunction name="testCombo" returntype="boolean">
<cfargument name="currentCombo" type="string" required="true" />
<cfargument name="currentTotal" type="numeric" required="true" />
<cfargument name="apps" type="array" required="true" />
<cfset var a = 0 />
<cfset var found = false />
<cfloop from="1" to="#arrayLen(arguments.apps)#" index="a">
<cfset arguments.currentCombo = listAppend(arguments.currentCombo, arguments.apps[a].name) />
<cfset arguments.currentTotal = arguments.currentTotal + arguments.apps[a].cost />
<cfif arguments.currentTotal eq 15.05>
<!--- print current combo --->
<cfoutput><strong>#arguments.currentCombo# = 15.05</strong></cfoutput><br />
<cfreturn true />
<cfelseif arguments.currentTotal gt 15.05>
<cfoutput>#arguments.currentCombo# > 15.05 (aborting)</cfoutput><br />
<cfreturn false />
<cfelse>
<!--- less than 15.05 --->
<cfoutput>#arguments.currentCombo# < 15.05 (traversing)</cfoutput><br />
<cfset found = testCombo(arguments.currentCombo, arguments.currentTotal, arguments.apps) />
</cfif>
</cfloop>
</cffunction>
<cfset mf = {name="Mixed Fruit", cost=2.15} />
<cfset ff = {name="French Fries", cost=2.75} />
<cfset ss = {name="side salad", cost=3.35} />
<cfset hw = {name="hot wings", cost=3.55} />
<cfset ms = {name="moz sticks", cost=4.20} />
<cfset sp = {name="sampler plate", cost=5.80} />
<cfset apps = [ mf, ff, ss, hw, ms, sp ] />
<cfloop from="1" to="6" index="b">
<cfoutput>#testCombo(apps[b].name, apps[b].cost, apps)#</cfoutput>
</cfloop>
El código anterior me dice que la única combinación que suma $ 15.05 es 7 órdenes de Mixed Fruit, y se requieren 232 ejecuciones de la función testCombo para completar.
¿Existe un algoritmo mejor para llegar a la solución correcta? ¿Llegué a la solución correcta?
Solución
El punto sobre un problema de NP-completo no es que sea complicado en un conjunto de datos pequeño, sino que la cantidad de trabajo para resolverlo crece a una tasa mayor que la del polinomio, es decir, no hay un algoritmo O (n ^ x) .
Si la complejidad del tiempo es O (n!), como en (creo) los dos problemas mencionados anteriormente, eso es en NP.
Otros consejos
Da todas las permutaciones de las soluciones, pero creo que estoy superando a todos los demás por el tamaño del código.
item(X) :- member(X,[215, 275, 335, 355, 420, 580]).
solution([X|Y], Z) :- item(X), plus(S, X, Z), Z >= 0, solution(Y, S).
solution([], 0).
Solución con swiprolog:
?- solution(X, 1505).
X = [215, 215, 215, 215, 215, 215, 215] ;
X = [215, 355, 355, 580] ;
X = [215, 355, 580, 355] ;
X = [215, 580, 355, 355] ;
X = [355, 215, 355, 580] ;
X = [355, 215, 580, 355] ;
X = [355, 355, 215, 580] ;
X = [355, 355, 580, 215] ;
X = [355, 580, 215, 355] ;
X = [355, 580, 355, 215] ;
X = [580, 215, 355, 355] ;
X = [580, 355, 215, 355] ;
X = [580, 355, 355, 215] ;
No
¿No es más elegante con la recursión (en Perl)?
#!/usr/bin/perl
use strict;
use warnings;
my @weights = (2.15, 2.75, 3.35, 3.55, 4.20, 5.80);
my $total = 0;
my @order = ();
iterate($total, @order);
sub iterate
{
my ($total, @order) = @_;
foreach my $w (@weights)
{
if ($total+$w == 15.05)
{
print join (', ', (@order, $w)), "\n";
}
if ($total+$w < 15.05)
{
iterate($total+$w, (@order, $w));
}
}
}
Salida
marco @ unimatrix-01: ~ $ ./xkcd-knapsack.pl
2.15, 2.15, 2.15, 2.15, 2.15, 2.15, 2.15
2.15, 3.55, 3.55, 5.8
2.15, 3.55, 5.8, 3.55
2.15, 5.8, 3.55, 3.55
3.55, 2.15, 3.55, 5.8
3.55, 2.15, 5.8, 3.55
3.55, 3.55, 2.15, 5.8
3.55, 5.8, 2.15, 3.55
5.8, 2.15, 3.55, 3.55
5.8, 3.55, 2.15, 3.55
Aunque la mochila está completa, es un problema muy especial: el programa dinámico habitual es excelente ( http://en.wikipedia.org/wiki/Knapsack_problem )
Y si realiza el análisis correcto, resulta que es O (nW), n es el número de elementos y W es el número objetivo. El problema es que cuando se tiene que DP sobre una W grande, es cuando obtenemos el comportamiento de NP. Pero en su mayor parte, la mochila se comporta razonablemente bien y puede resolver instancias realmente grandes sin problemas. En cuanto a los problemas completos de NP, la mochila es una de las más fáciles.
Aquí está la solución que usa restriccion.py
>>> from constraint import *
>>> problem = Problem()
>>> menu = {'mixed-fruit': 2.15,
... 'french-fries': 2.75,
... 'side-salad': 3.35,
... 'hot-wings': 3.55,
... 'mozarella-sticks': 4.20,
... 'sampler-plate': 5.80}
>>> for appetizer in menu:
... problem.addVariable( appetizer, [ menu[appetizer] * i for i in range( 8 )] )
>>> problem.addConstraint(ExactSumConstraint(15.05))
>>> problem.getSolutions()
[{'side-salad': 0.0, 'french-fries': 0.0, 'sampler-plate': 5.7999999999999998, 'mixed-fruit': 2.1499999999999999, 'mozarella-sticks': 0.0, 'hot-wings': 7.0999999999999996},
{'side-salad': 0.0, 'french-fries': 0.0, 'sampler-plate': 0.0, 'mixed-fruit': 15.049999999999999, 'mozarella-sticks': 0.0, 'hot-wings': 0.0}]
Así que la solución es pedir una placa de muestra, una fruta mixta y 2 órdenes de alitas calientes, o pedir 7 frutas mixtas.
Aquí hay una solución con F #:
#light
type Appetizer = { name : string; cost : int }
let menu = [
{name="fruit"; cost=215}
{name="fries"; cost=275}
{name="salad"; cost=335}
{name="wings"; cost=355}
{name="moz sticks"; cost=420}
{name="sampler"; cost=580}
]
// Choose: list<Appetizer> -> list<Appetizer> -> int -> list<list<Appetizer>>
let rec Choose allowedMenu pickedSoFar remainingMoney =
if remainingMoney = 0 then
// solved it, return this solution
[ pickedSoFar ]
else
// there's more to spend
[match allowedMenu with
| [] -> yield! [] // no more items to choose, no solutions this branch
| item :: rest ->
if item.cost <= remainingMoney then
// if first allowed is within budget, pick it and recurse
yield! Choose allowedMenu (item :: pickedSoFar) (remainingMoney - item.cost)
// regardless, also skip ever picking more of that first item and recurse
yield! Choose rest pickedSoFar remainingMoney]
let solutions = Choose menu [] 1505
printfn "%d solutions:" solutions.Length
solutions |> List.iter (fun solution ->
solution |> List.iter (fun item -> printf "%s, " item.name)
printfn ""
)
(*
2 solutions:
fruit, fruit, fruit, fruit, fruit, fruit, fruit,
sampler, wings, wings, fruit,
*)
Lea el Problema de mochila .
Ya tiene todas las combinaciones correctas, pero aún está comprobando muchas más de las que necesita (como lo demuestran las numerosas permutaciones que muestra su resultado). Además, estás omitiendo el último elemento que llega a la marca de 15.05.
Tengo una versión de PHP que hace 209 iteraciones de la llamada recursiva (hace 2012 si recibo todas las permutaciones). Puede reducir su conteo si justo antes del final de su ciclo, saca el elemento que acaba de marcar.
No sé la sintaxis de CF, pero será algo como esto:
<cfelse>
<!--- less than 15.50 --->
<!--<cfoutput>#arguments.currentCombo# < 15.05 (traversing)</cfoutput><br />-->
<cfset found = testCombo(CC, CT, arguments.apps) />
------- remove the item from the apps array that was just checked here ------
</cfif>
</cfloop>
EDITAR: Para referencia, aquí está mi versión de PHP:
<?
function rc($total, $string, $m) {
global $c;
$m2 = $m;
$c++;
foreach($m as $i=>$p) {
if ($total-$p == 0) {
print "$string $i\n";
return;
}
if ($total-$p > 0) {
rc($total-$p, $string . " " . $i, $m2);
}
unset($m2[$i]);
}
}
$c = 0;
$m = array("mf"=>215, "ff"=>275, "ss"=>335, "hw"=>355, "ms"=>420, "sp"=>580);
rc(1505, "", $m);
print $c;
?>
Salida
mf mf mf mf mf mf mf
mf hw hw sp
209
EDIT 2:
Dado que explicar por qué puedes eliminar los elementos, llevará un poco más de lo que podría incluir en un comentario, lo estoy agregando aquí.
Básicamente, cada recursión encontrará todas las combinaciones que incluyen el elemento de búsqueda actual (por ejemplo, el primer paso encontrará todo, incluyendo al menos una fruta mezclada). La forma más fácil de entenderlo es rastrear la ejecución, pero como eso tomará mucho espacio, lo haré como si el objetivo fuera 6.45.
MF (2.15)
MF (4.30)
MF (6.45) *
FF (7.05) X
SS (7.65) X
...
[MF removed for depth 2]
FF (4.90)
[checking MF now would be redundant since we checked MF/MF/FF previously]
FF (7.65) X
...
[FF removed for depth 2]
SS (5.50)
...
[MF removed for depth 1]
En este punto, hemos comprobado todas las combinaciones que incluyen cualquier fruta mixta, por lo que no hay necesidad de revisar la fruta mezclada nuevamente. También puede usar la misma lógica para podar la matriz en cada una de las recursiones más profundas.
El rastreo a través de él de esta manera en realidad sugirió otro ahorro de tiempo: saber que los precios están ordenados de bajo a alto significa que no necesitamos seguir revisando los artículos una vez que superamos el objetivo.
Haría una sugerencia sobre el diseño del propio algoritmo (que es como interpreté la intención de su pregunta original). Aquí hay un fragmento de la solución que escribí:
....
private void findAndReportSolutions(
int target, // goal to be achieved
int balance, // amount of goal remaining
int index // menu item to try next
) {
++calls;
if (balance == 0) {
reportSolution(target);
return; // no addition to perfect order is possible
}
if (index == items.length) {
++falls;
return; // ran out of menu items without finding solution
}
final int price = items[index].price;
if (balance < price) {
return; // all remaining items cost too much
}
int maxCount = balance / price; // max uses for this item
for (int n = maxCount; 0 <= n; --n) { // loop for this item, recur for others
++loops;
counts[index] = n;
findAndReportSolutions(
target, balance - n * price, index + 1
);
}
}
public void reportSolutionsFor(int target) {
counts = new int[items.length];
calls = loops = falls = 0;
findAndReportSolutions(target, target, 0);
ps.printf("%d calls, %d loops, %d falls%n", calls, loops, falls);
}
public static void main(String[] args) {
MenuItem[] items = {
new MenuItem("mixed fruit", 215),
new MenuItem("french fries", 275),
new MenuItem("side salad", 335),
new MenuItem("hot wings", 355),
new MenuItem("mozzarella sticks", 420),
new MenuItem("sampler plate", 580),
};
Solver solver = new Solver(items);
solver.reportSolutionsFor(1505);
}
...
(Tenga en cuenta que el constructor sí ordena los elementos del menú aumentando el precio, para permitir la terminación anticipada de tiempo constante cuando el saldo restante es más pequeño que cualquier otro elemento del menú).
La salida para una ejecución de muestra es:
7 mixed fruit (1505) = 1505
1 mixed fruit (215) + 2 hot wings (710) + 1 sampler plate (580) = 1505
348 calls, 347 loops, 79 falls
La sugerencia de diseño que quiero resaltar es que en el código anterior, cada llamada anidada (recursiva) de findAndReportSolution (...) se ocupa de la cantidad de exactamente un elemento del menú, identificado por el index argumento. En otras palabras, el anidamiento recursivo es paralelo al comportamiento de un conjunto en línea de bucles anidados; la parte más externa cuenta los posibles usos del primer elemento del menú, la siguiente cuenta los usos del segundo elemento del menú, etc. (Excepto, por supuesto, el uso de la recursión libera el código de la dependencia de un número específico de elementos del menú). / p>
Sugiero que esto facilita el diseño del código y la comprensión de lo que hace cada invocación (explicando todos los usos posibles de un elemento específico, delegando el resto del menú a las llamadas subordinadas). También evita la explosión combinatoria de producir todas las disposiciones de una solución de elementos múltiples (como en la segunda línea de la salida anterior, que solo ocurre una vez, en lugar de repetidamente con diferentes ordenamientos de los artículos).
Intento maximizar la " obviedad " del código, en lugar de intentar minimizar el número de llamadas de algún método específico. Por ejemplo, el diseño anterior permite que una llamada delegada determine si se ha llegado a una solución, en lugar de ajustar esa comprobación alrededor del punto de la llamada, lo que reduciría el número de llamadas a costa de saturar el código.
Hmm, sabes lo que es raro. La solución es siete del primer elemento del menú.
Como obviamente esto se resolvió con papel y lápiz en un corto período de tiempo, ¿por qué no dividir el total del pedido por el precio de cada artículo para ver si por alguna posibilidad ordenaron múltiplos de un artículo?
Por ejemplo,
15.05 / 2.15 = 7 frutas mezcladas 15.05 / 2.75 = 5.5 papas fritas.
Y luego pasar a combinaciones simples ...
15 / (2.15 + 2.75) = 3.06122449 frutas mezcladas con papas fritas.
En otras palabras, suponga que la solución debe ser simple y solucionable para un humano sin acceso a una computadora. Luego pruebe si la (s) solución (es) más simple, más obvia (y, por lo tanto, oculta a simple vista) funciona.
Juro que voy a hacer esto en el local este fin de semana cuando ordene $ 4,77 en aperitivos (impuestos incluidos) a las 4:30 AM después de que el club cierre.
En python.
Tuve algunos problemas con " vars globales " Así que puse la función como método de un objeto. Es recursivo y se llama a sí mismo 29 veces por la pregunta en el cómic, deteniéndose en la primera coincidencia exitosa
class Solver(object):
def __init__(self):
self.solved = False
self.total = 0
def solve(s, p, pl, curList = []):
poss = [i for i in sorted(pl, reverse = True) if i <= p]
if len(poss) == 0 or s.solved:
s.total += 1
return curList
if abs(poss[0]-p) < 0.00001:
s.solved = True # Solved it!!!
s.total += 1
return curList + [poss[0]]
ml,md = [], 10**8
for j in [s.solve(p-i, pl, [i]) for i in poss]:
if abs(sum(j)-p)<md: ml,md = j, abs(sum(j)-p)
s.total += 1
return ml + curList
priceList = [5.8, 4.2, 3.55, 3.35, 2.75, 2.15]
appetizers = ['Sampler Plate', 'Mozzarella Sticks', \
'Hot wings', 'Side salad', 'French Fries', 'Mixed Fruit']
menu = zip(priceList, appetizers)
sol = Solver()
q = sol.solve(15.05, priceList)
print 'Total time it runned: ', sol.total
print '-'*30
order = [(m, q.count(m[0])) for m in menu if m[0] in q]
for o in order:
print '%d x %s \t\t\t (%.2f)' % (o[1],o[0][1],o[0][0])
print '-'*30
ts = 'Total: %.2f' % sum(q)
print ' '*(30-len(ts)-1),ts
Salida:
Total time it runned: 29
------------------------------
1 x Sampler Plate (5.80)
2 x Hot wings (3.55)
1 x Mixed Fruit (2.15)
------------------------------
Total: 15.05
En realidad, he refactorizado mi algoritmo un poco más. Había varias combinaciones correctas que faltaba, y se debía al hecho de que regresaba tan pronto como el costo superaba los 15.05. No me molestaba en comprobar otros artículos (más baratos) que pudiera agregar. Aquí está mi nuevo algoritmo:
<cffunction name="testCombo" returntype="numeric">
<cfargument name="currentCombo" type="string" required="true" />
<cfargument name="currentTotal" type="numeric" required="true" />
<cfargument name="apps" type="array" required="true" />
<cfset var a = 0 />
<cfset var found = false />
<cfset var CC = "" />
<cfset var CT = 0 />
<cfset tries = tries + 1 />
<cfloop from="1" to="#arrayLen(arguments.apps)#" index="a">
<cfset combos = combos + 1 />
<cfset CC = listAppend(arguments.currentCombo, arguments.apps[a].name) />
<cfset CT = arguments.currentTotal + arguments.apps[a].cost />
<cfif CT eq 15.05>
<!--- print current combo --->
<cfoutput><strong>#CC# = 15.05</strong></cfoutput><br />
<cfreturn true />
<cfelseif CT gt 15.05>
<!--<cfoutput>#arguments.currentCombo# > 15.05 (aborting)</cfoutput><br />-->
<cfelse>
<!--- less than 15.50 --->
<!--<cfoutput>#arguments.currentCombo# < 15.05 (traversing)</cfoutput><br />-->
<cfset found = testCombo(CC, CT, arguments.apps) />
</cfif>
</cfloop>
<cfreturn found />
</cffunction>
<cfset mf = {name="Mixed Fruit", cost=2.15} />
<cfset ff = {name="French Fries", cost=2.75} />
<cfset ss = {name="side salad", cost=3.35} />
<cfset hw = {name="hot wings", cost=3.55} />
<cfset ms = {name="moz sticks", cost=4.20} />
<cfset sp = {name="sampler plate", cost=5.80} />
<cfset apps = [ mf, ff, ss, hw, ms, sp ] />
<cfset tries = 0 />
<cfset combos = 0 />
<cfoutput>
<cfloop from="1" to="6" index="b">
#testCombo(apps[b].name, apps[b].cost, apps)#
</cfloop>
<br />
tries: #tries#<br />
combos: #combos#
</cfoutput>
Salida:
Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit,Mixed Fruit = 15.05
Mixed Fruit,hot wings,hot wings,sampler plate = 15.05
Mixed Fruit,hot wings,sampler plate,hot wings = 15.05
Mixed Fruit,sampler plate,hot wings,hot wings = 15.05
false false false hot wings,Mixed Fruit,hot wings,sampler plate = 15.05
hot wings,Mixed Fruit,sampler plate,hot wings = 15.05
hot wings,hot wings,Mixed Fruit,sampler plate = 15.05
hot wings,sampler plate,Mixed Fruit,hot wings = 15.05
false false sampler plate,Mixed Fruit,hot wings,hot wings = 15.05
sampler plate,hot wings,Mixed Fruit,hot wings = 15.05
false
tries: 2014
combos: 12067
Creo que esto puede tener todas las combinaciones correctas, pero mi pregunta sigue en pie: ¿Existe un algoritmo mejor?
Aprendiendo de @ respuesta de rcar , y otra refactorización más tarde, tengo lo siguiente.
Como con tantas cosas que codifico, he refactorizado de CFML a CFScript, pero el código es básicamente el mismo.
Agregué su sugerencia de un punto de inicio dinámico en la matriz (en lugar de pasar la matriz por valor y cambiar su valor para futuras recursiones), lo que me llevó a las mismas estadísticas que obtiene (209 recursiones, 571 combinaciones de precios). (repeticiones de bucle)), y luego mejoró eso al suponer que la matriz se ordenará por costo (porque es) y se romperá tan pronto como superemos el precio objetivo. Con el descanso, hemos bajado a 209 recursiones y 376 iteraciones de bucle.
¿Qué otras mejoras se podrían hacer al algoritmo?
function testCombo(minIndex, currentCombo, currentTotal){
var a = 0;
var CC = "";
var CT = 0;
var found = false;
tries += 1;
for (a=arguments.minIndex; a <= arrayLen(apps); a++){
combos += 1;
CC = listAppend(arguments.currentCombo, apps[a].name);
CT = arguments.currentTotal + apps[a].cost;
if (CT eq 15.05){
//print current combo
WriteOutput("<strong>#CC# = 15.05</strong><br />");
return(true);
}else if (CT gt 15.05){
//since we know the array is sorted by cost (asc),
//and we've already gone over the price limit,
//we can ignore anything else in the array
break;
}else{
//less than 15.50, try adding something else
found = testCombo(a, CC, CT);
}
}
return(found);
}
mf = {name="mixed fruit", cost=2.15};
ff = {name="french fries", cost=2.75};
ss = {name="side salad", cost=3.35};
hw = {name="hot wings", cost=3.55};
ms = {name="mozarella sticks", cost=4.20};
sp = {name="sampler plate", cost=5.80};
apps = [ mf, ff, ss, hw, ms, sp ];
tries = 0;
combos = 0;
testCombo(1, "", 0);
WriteOutput("<br />tries: #tries#<br />combos: #combos#");
Aquí hay implementación concurrente en Clojure. Para calcular (artículos con precio 15.05) se necesitan aproximadamente 14 recursiones de generación combinada y aproximadamente 10 verificaciones de posibilidad. Me tomó aproximadamente 6 minutos calcular el (artículos con precio 100) en mi Intel Q9300.
Esto solo da la primera respuesta encontrada, o nil si no hay ninguna, ya que ese es el único problema que requiere. ¿Por qué hacer más trabajo que le han dicho que haga?)?
;; np-complete.clj
;; A Clojure solution to XKCD #287 "NP-Complete"
;; By Sam Fredrickson
;;
;; The function "items-with-price" returns a sequence of items whose sum price
;; is equal to the given price, or nil.
(defstruct item :name :price)
(def *items* #{(struct item "Mixed Fruit" 2.15)
(struct item "French Fries" 2.75)
(struct item "Side Salad" 3.35)
(struct item "Hot Wings" 3.55)
(struct item "Mozzarella Sticks" 4.20)
(struct item "Sampler Plate" 5.80)})
(defn items-with-price [price]
(let [check-count (atom 0)
recur-count (atom 0)
result (atom nil)
checker (agent nil)
; gets the total price of a seq of items.
items-price (fn [items] (apply + (map #(:price %) items)))
; checks if the price of the seq of items matches the sought price.
; if so, it changes the result atom. if the result atom is already
; non-nil, nothing is done.
check-items (fn [unused items]
(swap! check-count inc)
(if (and (nil? @result)
(= (items-price items) price))
(reset! result items)))
; lazily generates a list of combinations of the given seq s.
; haven't tested well...
combinations (fn combinations [cur s]
(swap! recur-count inc)
(if (or (empty? s)
(> (items-price cur) price))
'()
(cons cur
(lazy-cat (combinations (cons (first s) cur) s)
(combinations (cons (first s) cur) (rest s))
(combinations cur (rest s))))))]
; loops through the combinations of items, checking each one in a thread
; pool until there are no more combinations or the result atom is non-nil.
(loop [items-comb (combinations '() (seq *items*))]
(if (and (nil? @result)
(not-empty items-comb))
(do (send checker check-items (first items-comb))
(recur (rest items-comb)))))
(await checker)
(println "No. of recursions:" @recur-count)
(println "No. of checks:" @check-count)
@result))
Si desea un algoritmo optimizado, es mejor probar los precios en orden descendente. Eso le permite usar la mayor parte de la cantidad restante primero y luego ver cómo se puede completar el resto.
También, puedes usar las matemáticas para calcular la cantidad máxima de cada alimento para comenzar cada vez, así que no intentes combinaciones que superen la meta de $ 15.05.
Este algoritmo solo necesita probar 88 combinaciones para obtener una respuesta completa y parece el más bajo que se ha publicado hasta ahora:
public class NPComplete {
private static final int[] FOOD = { 580, 420, 355, 335, 275, 215 };
private static int tries;
public static void main(String[] ignore) {
tries = 0;
addFood(1505, "", 0);
System.out.println("Combinations tried: " + tries);
}
private static void addFood(int goal, String result, int index) {
// If no more food to add, see if this is a solution
if (index >= FOOD.length) {
tries++;
if (goal == 0)
System.out.println(tries + " tries: " + result.substring(3));
return;
}
// Try all possible quantities of this food
// If this is the last food item, only try the max quantity
int qty = goal / FOOD[index];
do {
addFood(goal - qty * FOOD[index],
result + " + " + qty + " * " + FOOD[index], index + 1);
} while (index < FOOD.length - 1 && --qty >= 0);
}
}
Aquí está la salida que muestra las dos soluciones:
9 tries: 1 * 580 + 0 * 420 + 2 * 355 + 0 * 335 + 0 * 275 + 1 * 215 88 tries: 0 * 580 + 0 * 420 + 0 * 355 + 0 * 335 + 0 * 275 + 7 * 215 Combinations tried: 88
