Die Lösung des NP-vollständigen Problems in XKCD
https://stackoverflow.com/questions/141779
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Das problem/komische in Frage: http://xkcd.com/287/
Ich bin mir nicht sicher, ob dies der beste Weg, es zu tun, aber hier ist, was ich mir ausgedacht habe, so weit.Ich bin mit CFML, aber es sollte von allen Benutzern gelesen werden.
<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>
Der obige code sagt mir, dass die einzige Kombination, die fügt bis zu $15.05 7 Bestellungen von Gemischten Früchten, und es dauert 232 Ausführungen meiner testCombo Funktion zu vollenden.
Gibt es einen besseren Algorithmus zu kommen auf die richtige Lösung?Kam ich auf die richtige Lösung?
Lösung
Der Punkt, um ein NP-vollständiges problem ist nicht, dass es ist schwierig, auf einer kleinen Datenmenge, sondern dass die Menge der Arbeit, es zu lösen, wächst mit einer rate, die größer als Polynom, alsoes ist nicht O(n^x) - Algorithmus.
Wenn die Zeit, die Komplexität ist O(n!), wie bei (ich glaube) die beiden oben erwähnten Probleme, die in NP.
Andere Tipps
Es gibt alle Permutationen der Lösungen, aber ich denke, ich bin schlagen alle anderen für die code-Größe.
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).
Lösung mit 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
Ist es nicht mehr elegant mit Rekursion (in 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));
}
}
}
Ausgabe
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
Obwohl knapsack ist NP-Vollständig, es ist ein sehr spezielles problem:die üblichen dynamisches Programm, denn es ist in der Tat sehr gut (http://en.wikipedia.org/wiki/Knapsack_problem)
Und wenn Sie die richtige Analyse, es stellt sich heraus, dass es O(nW), wobei n die Anzahl der Elemente, und W wird die Ziel-Nummer.Das problem ist, wenn Sie zur DP über ein großes W, das ist, wenn wir die NP-Verhalten.Aber für die meisten Teil, Ranzen ist Recht gut benommen und Sie lösen wirklich große Instanzen von es ohne Probleme.Soweit NP-vollständige Probleme gehen, Rucksack ist eine der einfachsten.
Hier ist die Lösung mit 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}]
Also die Lösung ist, um eine sampler-Platte, einen gemischten Früchten, und 2 Bestellungen von hot wings, oder bestellen Sie die 7 gemischte Früchte.
Hier ist eine Lösung in 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,
*)
Lesen Sie auf der Knapsack Problem.
Sie haben alle die richtigen Kombinationen jetzt, aber du bist immer noch überprüfen viele mehr, als Sie brauchen, um (wie belegt durch die vielen Variationsmöglichkeiten Ihr Ergebnis zeigt).Außerdem können Sie weglassen, das Letzte Element, das trifft den 15.05 mark.
Ich habe eine PHP-version 209 Iterationen des rekursiven Aufrufs ist (es ist 2012, wenn ich alle Permutationen).Reduzieren Sie Ihre Anzahl, wenn kurz vor dem Ende Ihrer Schleife, ziehen Sie das Element, das Sie gerade überprüft.
Ich weiß nicht, CF-syntax, aber es wird so etwas wie dieses:
<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:Für Referenz, hier ist meine PHP-version:
<?
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;
?>
Ausgabe
mf mf mf mf mf mf mf
mf hw hw sp
209
EDIT 2:
Seit erklären, warum Sie können entfernen Sie die Elemente dann ein wenig mehr, als ich konnte passen in einen Kommentar, ich bin das hinzufügen es hier.
Im Grunde, jede Rekursion finden Sie alle Kombinationen, die sich inklusive der aktuell gesuchten element (z.B., im ersten Schritt wird hier alles finden, darunter mindestens eine gemischte Früchte).Der einfachste Weg zu verstehen, ist es auf die Spur, die Ausführung, aber da, nehmen eine Menge Platz, ich werde es tun, als wenn das Ziel war, 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]
An diesem Punkt, wir haben überprüft alle-Kombination, die umfasst alle gemischten Früchten, so gibt es keine Notwendigkeit zu überprüfen für gemischten Früchten wieder.Sie können die gleiche Logik zu beschneiden, das array an jedem der tiefer rekursionen als gut.
Tracing durch, wie diese tatsächlich schlug eine andere leichte Zeit Bildschirmschoner-zu wissen, die Preise sind sortiert niedrig zu hoch bedeutet, dass wir brauchen nicht zu halten die überprüfung Artikel einmal wir gehen über das Ziel.
Ich würde einen Vorschlag über die Gestaltung der Algorithmus selbst (das ist, wie ich interpretiert die Absicht deiner ursprünglichen Frage).Hier ist eine fragment die Lösung, die ich schrieb:
....
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);
}
...
(Beachten Sie, dass der Konstruktor tut die Sortierung der Menüpunkte durch erhöhen Preis, zu aktivieren die Konstante-Zeit die vorzeitige Kündigung, wenn der Restbetrag geringer ist als alle übrigen Menüpunkt.)
Die Ausgabe für ein Beispiel ausgeführt wird:
7 mixed fruit (1505) = 1505
1 mixed fruit (215) + 2 hot wings (710) + 1 sampler plate (580) = 1505
348 calls, 347 loops, 79 falls
Der design-Vorschlag, den ich hervorheben möchte, ist, dass in dem obigen code, jede geschachtelte (rekursiven) Aufruf findAndReportSolution(...) befasst sich mit der Menge genau ein Menü, gekennzeichnet durch die index argument.In anderen Worten, die rekursive Verschachtelung von parallels und das Verhalten der in-line-Reihe von verschachtelten Schleifen;die äußerste zählt die Nutzungsmöglichkeiten der erste Menüpunkt, der nächste in der zählt, verwendet der zweite Menüpunkt, etc.(Außer, natürlich, die Verwendung von Rekursion befreit den code von der Abhängigkeit von einer bestimmten Anzahl von Menüpunkten!)
Ich schlage vor, dass diese macht es einfacher zu design die code, und leichter zu verstehen, was mit jedem Aufruf tut (accounting für alle möglichen Verwendungen eines bestimmten Elements, delegieren Sie den Rest des Menüs zu untergeordneten Anrufe).Es vermeidet auch die kombinatorische explosion der Herstellung alle arrangements von Multi-Element-Lösung (wie in der zweiten Zeile der obigen Ausgabe, die nur einmal vorkommt, statt immer wieder mit anderen Ordnungen der Elemente).
Ich versuchen zu maximieren die "Offensichtlichkeit" der code, anstatt zu versuchen, minimieren Sie die Anzahl der Anrufe für eine bestimmte Methode.Für Beispiel, die oben design ermöglicht einen Delegierten rufen Sie bestimmen, ob eine Lösung erreicht worden, anstatt-Verpackung, die sich rund um den Punkt des Aufrufs, die Verringerung der Anzahl von anrufen auf Kosten von überladen bis der code.
Hmm, weißt du, was komisch ist.Die Lösung ist sieben das erste Element auf der Speisekarte.
Da dies offensichtlich soll gelöst werden, indem Papier und Bleistift in einem kurzen Zeitrahmen, warum nicht teilen Sie den Gesamtbetrag durch den Preis von jeder Sache zu sehen, wenn durch Zufall Sie bestellt multiples of one item?
Für Beispiel,
15.05 Uhr/2.15 = 7 gemischte Früchte 15.05/2.75 = 5.5 Pommes Frites.
Und dann bewegen auf zu einfache Kombinationen...
15 / (2.15 + 2.75) = 3.06122449 gemischte Früchte mit Pommes Frites.
In anderen Worten, davon aus, dass die Lösung soll einfach und lösbar von einem Menschen ohne Zugang zu einem computer.Testen Sie dann, wenn die einfachsten und offensichtlichsten (und daher versteckt in plain sight) Lösung(s) Arbeit(en).
Ich schwöre, ich bin ziehen an der lokalen coney dieses Wochenende, wenn ich, um $4.77 Wert von Vorspeisen (einschließlich UST.) auf 4:30 UHR an, nachdem der club schließt.
In python.
Ich hatte einige Probleme mit "global vars" so lege ich die Funktion als Methode eines Objekts.Es ist rekursiv und es nennt sich 29-mal für die Frage in der comic, mit halt an der ersten erfolgreichen match
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
Ausgabe:
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
Eigentlich hab ich umgestaltet mein Algorithmus einige mehr.Es gab mehrere richtige Kombinationen die mir fehlte, und es war aufgrund der Tatsache, dass ich zurückkehren, sobald die Kosten ging über 15.05 -- ich war mir nicht die Mühe zu überprüfen, andere (günstigere) Artikel, die ich hinzufügen könnte.Hier ist meine neue Algorithmus:
<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>
Ausgabe:
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
Ich denke, das haben alle die richtigen Kombinationen, aber meine Frage steht immer noch:Gibt es einen besseren Algorithmus?
Lernen von @rcar Antwort, und ein weiteres refactoring später, habe ich die folgenden.
Wie bei so vielen Dingen, die ich code habe ich umgestalteten von CFML CFScript, aber der code ist im Grunde das gleiche.
Ich fügte hinzu, in seinem Vorschlag einer dynamischen start in das array (statt der übergabe des Arrays durch Wert und ändern dessen Wert für die Zukunft rekursionen), die mich dazu brachte, die gleichen stats bekommt er (209 rekursionen, 571 Kombination aus Preis-Prüfungen (schleifendurchläufe)), und dann verbessert auf, dass von der Annahme, dass das array sortiert werden, indem Sie Kosten-denn es ist-und brechen so bald wie wir gehen über die Ziel Preis.Mit der Pause sind wir zu 209 rekursionen und 376 loop-Iterationen.
Welche anderen Verbesserungen gemacht werden könnten, um den Algorithmus?
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#");
Hier ist die gleichzeitige Umsetzung in Clojure.Berechnen (items-with-price 15.05) dauert etwa 14 Kombination generation rekursionen, und über 10 Möglichkeiten überprüft.Hat mich etwa 6 Minuten zu berechnen (items-with-price 100) auf meinem Intel Q9300.
Dies gibt nur die erste Antwort darauf gefunden, oder nil wenn es keine gibt, wie das ist, alle das problem erfordert.Warum mehr arbeiten, haben Sie gesagt wurde, zu tun ;) ?
;; 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))
Wenn Sie möchten, eine optimierte Algorithmus, es ist am besten zu versuchen, die Preise in absteigender Reihenfolge.Das können Sie verwenden, so viel von der verbleibenden Menge zuerst und dann sehen, wie der rest ausgefüllt werden kann.
Auch, Sie können verwenden Sie Mathematik, um herauszufinden, die maximale Menge der einzelnen Nahrungsmittel zu jeder Zeit, so dass Sie nicht versuchen, die Kombinationen, das würde gehen über die $15.05 Ziel.
Dieser Algorithmus muss nur versuchen, 88-Kombinationen, um eine vollständige Antwort und sieht wie die niedrigsten, die veröffentlicht worden ist, so weit:
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);
}
}
Hier ist die Ausgabe zeigt, dass die beiden Lösungen:
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
