Resolver el problema NP-completo en xkcd

Question

El problema/cómic en cuestión: http://xkcd.com/287/

No estoy seguro de que esta es la mejor manera de hacerlo, pero esto es lo que he llegado con tan lejos. Estoy usando CFML, pero debería ser legible por cualquiera.

<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 se suma a $ 15.05 es de 7 órdenes de fruta mezclada, y se tarda 232 ejecuciones de mi función testCombo para completar.

¿Hay algún algoritmo mejor para llegar a la solución correcta? ¿He llegado a la solución correcta?

Answer 1

El punto sobre un problema NP-completo no es que es difícil en un pequeño conjunto de datos, pero que la cantidad de trabajo para resolver crece a una tasa mayor que polinomio, es decir, no hay algoritmo O (n^x).

Si la complejidad del tiempo es O (n!), Como en (creo) los dos problemas mencionados anteriormente, que está en NP.

Answer 2

Lea en el Knapsack Problem.

Answer 3

En realidad, he refactorizado mi algoritmo un poco más. Hubo varias combinaciones correctas que me faltaba, y fue debido al hecho de que volvía tan pronto como el costo pasó de 15.05 - No me molestaba en consultar otros artículos (más baratos) que podía 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: ¿Hay una mejor algoritmo?

Answer 4

Ahora tiene todas las combinaciones correctas, pero todavía está comprobando muchas más de lo que necesita (como lo demuestran las muchas permutaciones que muestra el resultado). Además, está omitiendo el último elemento que alcanza la marca de 15.05.

Tengo una versión de PHP que realiza 209 iteraciones de la llamada recursiva (2012 si obtengo todas las permutaciones). Puedes reducir tu conteo si justo antes del final de tu ciclo, sacas el ítem que acabas de marcar.

No sé sintaxis 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> 

EDIT: Como 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:

Como explicar por qué puede eliminar los elementos tomará un poco más de lo que cabría 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 lo encontrará todo, incluida al menos una fruta mixta). La forma más fácil de entenderlo es rastrear la ejecución, pero como eso ocupará 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 incluye cualquier fruta mezclada, así que no hay necesidad de comprobar la fruta mezclada de nuevo. También puede usar la misma lógica para podar la matriz en cada una de las recursiones más profundas.

rastreo a través de él como esto llegó a sugerir otro ligero ahorro de tiempo - a sabiendas de los precios se ordenan de menor a altas medios que no necesitamos para mantener el control de artículos una vez que vayamos sobre el objetivo.

Answer 5

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, 
*) 

Answer 6

¿No es más elegante con la recursividad (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

Answer 7

Aprender de @rcar's answer, y otro refactorización más tarde, tengo la siguiente.

Como con tantas cosas que el código, he refactorizado de CFML a CFScript, pero el código es básicamente el mismo.

Añadí en 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 él (209 recurrencias, 571 precio de combinación cheques (iteraciones de bucle)), y luego mejorado en eso suponiendo que la matriz se ordenará por costo, porque lo es, y quebrará tan pronto como superemos el precio objetivo. Con el descanso, tenemos 209 recursiones y 376 iteraciones de bucle.

¿Qué otras mejoras podrían hacerse con el 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#"); 

Answer 8

A pesar de que la mochila es NP completo, es un problema muy especial: el programa de dinámica habitual ya que es en realidad una excelente (http://en.wikipedia.org/wiki/Knapsack_problem)

Y si lo hace el análisis correcto, resulta que es O (nW), n es el n. ° de elementos, y W es el número objetivo. El problema es cuando tienes que DP en una gran W, es cuando obtenemos el comportamiento NP. Pero en su mayor parte, la mochila se comporta razonablemente bien y puedes resolver instancias realmente grandes sin problemas. En lo que respecta a los problemas completos de NP, la mochila es una de las más fáciles.

Answer 9

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 SWI-Prolog:

?- 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 

Answer 10

Aquí está la solución usando constraint.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 para pedir un plato de selección, una fruta mezclada, y 2 órdenes de alas calientes, u ordene 7 frutas mixtas.

Answer 11

Haría una sugerencia sobre el diseño del algoritmo en sí (que es la forma en que interpreté la intención de su pregunta original). Aquí está 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 hace ordenar los elementos de menú mediante el aumento de precio, para permitir que la constante de tiempo de terminación anticipada cuando el saldo restante es menor que . cualquier elemento del menú restante)

la salida para una carrera de la 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 destacar es que en el anterior c ode, cada llamada anidada (recursiva) de findAndReportSolution(...) trata de la cantidad de exactamente un elemento del menú, identificado por el argumento index. En otras palabras, el anidamiento recursivo es paralelo al comportamiento de un conjunto en línea de bucles anidados; el más externo cuenta posibles usos del primer elemento del menú, el siguiente en 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 de menú!)

Sugiero que esto hace que sea más fácil diseñar el código, y más fácil de entender lo que hace cada invocación (teniendo en cuenta todos los usos posibles de un elemento específico, delegando el resto del menú a llamadas subordinadas). También evita la explosión combinatoria de producir todas las disposiciones de una solución de múltiples elementos (como en la segunda línea de la salida anterior, que solo se produce una vez, en lugar de repetidamente con diferentes ordenamientos de los elementos).

Intento maximizar la "obviedad" del código, en lugar de tratar de 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 alcanzado una solución, en lugar de ajustar esa verificación alrededor del punto de la llamada, lo que reduciría el número de llamadas a costa de saturar el código.

Answer 12

Hmm, sabes lo que es raro. La solución es siete del primer elemento en el menú.

Dado que esto estaba destinado a ser resuelto por papel y lápiz en un corto período de tiempo, ¿por qué no dividir el total de la orden por el precio de cada artículo para ver si por casualidad pedían múltiplos de un artículo?

Por ejemplo,

15,05/2,15 = 7 frutas mezcladas 15,05/2,75 = 5,5 patatas fritas.

Y luego pasar a combinaciones simples ...

15/(2,15 + 2,75) = 3.06122449 frutas mezcladas con las patatas fritas.

En otras palabras, suponga que la solución se supone que es simple y puede ser solucionada por un humano sin acceso a una computadora. Luego prueba si funciona (n) la (s) solución (es) más simple (s) y más obvia (y por lo tanto oculta a la vista).

Juro que estoy sacando esto en el coney local este fin de semana cuando ordeno $ 4.77 en aperitivos (impuestos incluidos) a las 4:30 a.m. después del cierre del club.

Answer 13

Aquí está la implementación concurrente en Clojure. Para calcular (items-with-price 15.05) se necesitan aproximadamente 14 recursiones de generación de combinación, y aproximadamente 10 verificaciones de posibilidad.Me llevó unos 6 minutos calcular (items-with-price 100) en mi Intel Q9300.

Esto solo da la primera respuesta encontrada, o nil si no hay ninguna, ya que eso es todo lo que necesita el problema. ¿Por qué hacer más trabajo que te han dicho que hagas?)?

;; 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)) 

Answer 14

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 para la pregunta en el cómic, con parada en la primera persona compatible

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 

Answer 15

Si desea un algoritmo optimizado, lo mejor es probar el precios en orden descendente. Eso le permite usar la mayor cantidad de la cantidad restante primero y luego ver cómo se puede completar el resto.

Además, puede usar las matemáticas para calcular la cantidad máxima de cada alimento para comenzar cada vez, así que Intente combinaciones que superarían el objetivo de $ 15.05.

Este algoritmo sólo tiene que tratar 88 combinaciones para conseguir una respuesta completa y que se parece a la más baja 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