Resolviendo el problema NP-complete en XKCD

Da todas las permutaciones de las soluciones, pero creo que estoy superando a todos los demás por tamaño de 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 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 knapsack es NP Completo, es un problema muy especial: el programa dinámico habitual para ello es de hecho excelente ( http://en.wikipedia.org/wiki/Knapsack_problem )

Y si haces el análisis correcto, resulta que es O(nW), n es el # de elementos, y W es el número objetivo. El problema es cuando tienes que DP sobre una W grande, es cuando obtenemos el comportamiento NP. Pero en su mayor parte, mochila es razonablemente bien comportado y se puede resolver muy grande ejemplos de ello sin problemas. En cuanto a los problemas completos de NP, knapsack es uno de los más fáciles.

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}]

Entonces, la solución es pedir un plato 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 sobre el problema de la mochila .

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

Tengo una versión de PHP que hace 209 iteraciones de la llamada recursiva (hace 2012 si obtengo todas las permutaciones). Usted puede reducir su número si justo antes del final de su bucle, saca el elemento que acaba de verificarse.

No conozco la 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>

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

EDITAR 2:

Dado que explicar por qué puedes eliminar los elementos tomará un poco más de lo que podría caber 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 cada combinación que incluye cualquier fruta mezclada, por lo que no hay necesidad de comprobar si hay 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.

Rastrearlo de esta manera en realidad sugirió otro ligero ahorro de tiempo knowing saber que los precios están ordenados de bajo a alto significa que no lo hacemos tenemos que seguir revisando los artículos una vez que pasemos por encima del objetivo.

Haría una sugerencia sobre el diseño del algoritmo en sí (que es cómo interpreté la intención de su pregunta original). He aquí 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 del menú aumentando el precio, para habilitar la terminación temprana en tiempo constante cuando el saldo restante es más pequeño que cualquier elemento del menú restante.)

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 I queremos resaltar que en el código anterior, cada llamada anidada (recursiva) de findAndReportSolution(...) trata con la cantidad de exactamente un elemento de 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 los posibles usos del primer elemento del menú, el siguiente in cuenta los usos del segundo elemento del menú, etc. (Excepto, por supuesto, el uso de recursión libera el código de la dependencia de un número específico de menú ¡artículos!)

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

Trato de maximice 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 envolver esa verificación alrededor del punto de la llamada, lo que reduciría el número de llamadas a expensas de saturar el código.

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

Dado que esto obviamente estaba destinado a ser resuelto 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 casualidad ordenaron múltiplos de un artículo?

Por ejemplo,

15.05/2.15 = 7 frutas mixtas 15.05 / 2.75 = 5.5 papas fritas.

Y luego pasar a combinaciones simples...

15 / (2.15 + 2.75) = 3.06122449 mezcla de frutas con patatas fritas.

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

Juro que estoy tirando de esto en el local coney este fin de semana cuando pido appeti 4.77 en aperitivos (impuestos incluidos) a las 4:30 AM después de que el club cierra.

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, deteniéndose en el primer partido exitoso

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 me faltaba, y fue debido al hecho de que regresaba tan pronto como el costo fue más de 15.05't No me molestaba en revisar 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: ¿Hay un algoritmo mejor?

Aprendiendo de la respuesta de@rcar, y otra refactorización más tarde, tengo lo siguiente.

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

Agregué 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 recursiones futuras), lo que me llevó a las mismas estadísticas que obtiene (209 recursiones, 571 comprobaciones de precios combinadas (iteraciones de bucle)), y luego mejorado en eso asumiendo que la matriz será ordenada por costo because porque es is y rompiendo tan pronto como vamos sobre el precio objetivo. Con la ruptura, nos quedamos con 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í está la implementación concurrente en Clojure. Para calcular (items-with-price 15.05) se necesitan unas 14 recursiones de generación de combinaciones y unas 10 comprobaciones de posibilidades. 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 el problema requiere. ¿Por qué hacer más trabajo que te han dicho que hacer ;) ?

;; 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 quieres un algoritmo optimizado, lo mejor es 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.

Además, puedes usar las matemáticas para calcular la cantidad máxima de cada alimento para comenzar cada vez para que no intentes combinaciones que superen el objetivo de $15.05.

Este algoritmo solo necesita probar 88 combinaciones para obtener una respuesta completa y que parece la más baja que ha sido 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