De problèmes NP-complets problème dans XKCD

Il donne toutes les permutations des solutions, mais je pense que je vais battre tout le monde pour la taille du code.

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

Solution avec 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

Même si le sac à dos est un problème NP Complet, c'est un problème très particulier: l'habitude dynamique de il est en fait excellent (http://en.wikipedia.org/wiki/Knapsack_problem)

Et si vous faites la bonne analyse, il s'avère que c'est O(nW), n étant le nombre d'éléments, et W étant le numéro de la cible. Le problème, c'est quand vous avez de la DP sur un grand W, c'est quand nous arrivons à la NP comportement. Mais pour la plupart, sac-à-dos est relativement bien comportés et vous pouvez résoudre vraiment grandes instances de sans problèmes. Aussi loin que NP complet problèmes, sac à dos est l'un des plus faciles.

Voici une solution avec 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,
*)

Vous avez toutes les bonnes combinaisons, mais vous êtes toujours en train de vérifier beaucoup plus que vous avez besoin d' (comme en témoigne le nombre de permutations de votre montre). Aussi, vous êtes en omettant le dernier élément qui frappe le 15.05 marque.

J'ai une version de PHP qui n'209 itérations de l'appel récursif (il n'2012 si je reçois toutes les permutations). Vous pouvez réduire votre compte si juste avant la fin de votre boucle, vous tirez sur l'élément que vous venez de vérifier.

Je ne sais pas CF syntaxe, mais ce sera quelque chose comme ceci:

        <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: Pour référence, voici ma version 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;
?>

Sortie

 mf mf mf mf mf mf mf
 mf hw hw sp
209

EDIT 2:

Depuis expliquant pourquoi vous pouvez supprimer les éléments prendra un petit plus que j'ai pu mettre dans un commentaire, je vais ajouter ici.

Fondamentalement, chaque récursion trouverez toutes les combinaisons comportant le actuellement à la recherche de l'élément (par exemple, la première étape sera de trouver de tout, y compris au moins une salade de fruits). La meilleure façon de le comprendre est de tracer l'exécution, mais depuis que va prendre beaucoup d'espace, je vais le faire comme si la cible était 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]

À ce stade, nous avons vérifié chaque combinaison qui comprend tout de la salade de fruits, il n'ya donc pas besoin de vérifier pour la salade de fruits à nouveau. Vous pouvez utiliser la même logique pour purger le tableau à chacun de la plus profonde récurrences ainsi.

Suivi par le biais de cette réalité a suggéré un autre léger gain de temps-la connaissance que les prix sont triés du plus faible au plus élevé signifie que nous n'avons pas besoin de garder le contrôle des éléments une fois que nous allons sur la cible.

Hmm, vous savez ce qui est bizarre. La solution est de sept du premier élément dans le menu.

Car ce n'était évidemment destiné à être résolu par le papier et crayon dans un court laps de temps, pourquoi ne pas diviser le total de la commande par le prix de chaque article pour voir si par hasard ils ont ordonné multiples d'un élément?

Par exemple,

15.05/2.15 = 7 fruits variés
15.05/2.75 = 5.5 frites.

Et de passer ensuite à des combinaisons simples...

15 /(2.15 + 2.75) = 3.06122449 fruits variés avec des frites.

En d'autres termes, supposons que la solution est censé être simple et résolubles par des humains sans accès à un ordinateur. Puis tester si le plus simple, le plus évident (et, par conséquent, hidden in plain sight) solution(s) œuvre(s).

Je vous jure que je suis en tirant la à la local de coney ce week-end lorsque je commande $4.77 valeur de hors-d'œuvre (y compris l'impôt) à 4:30 AM après la fermeture du club.

En fait, j'ai refait mon algorithme un peu plus. Il y avait plusieurs de corriger les combinaisons qui me manquait, et c'était dû au fait que j'étais de retour dès que le coût est allé sur 15.05 -- je n'étais pas la peine de vérifier d'autres (moins cher) des éléments que je pourrais ajouter. Voici mon nouvel algorithme:

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

De sortie:

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

Je pense que cela peut en avoir les bonnes combinaisons, mais ma question tient toujours: Est-il un meilleur algorithme?

Ici simultanées de mise en œuvre en Clojure. Pour calculer (items-with-price 15.05) prend environ 14 combinaison de génération de récurrences, et environ 10 possibilité de vérifications. M'a pris environ 6 minutes pour calculer le (items-with-price 100) sur mon Intel Q9300.

Cela ne donne que le premier a trouvé la réponse, ou nil si il n'y a aucune, c'est tout le problème des appels pour. Pourquoi faire plus de travail que vous avez dit de le faire 😉 ?

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