解決NP完全問題在XKCD

Question

問題問題/漫畫：http://xkcd.com/287/

我不知道這是做的最好的方式，但這裏是我想出什麼迄今爲止。我使用CFML，但它應該是任何人都可讀的。

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

上面的代碼告訴我，增加了高達$ 15.05的唯一組合是雜果7項目，它需要我testCombo功能的232個執行完成。

有沒有更好的算法來找到正確的解決方案？我有沒有找到正確的解決方案？

Answer 1

約NP完全問題的關鍵不在於它是在一個小的數據集棘手，但這項工作的量來解決它生長的速度更大比多項式，即沒有O（n^x）算法。

如果時間複雜度是O（n！），如在（我相信）上面提到的兩個問題，那就是NP。

Answer 2

請閱讀Knapsack Problem。

Answer 3

其實，我已經重構了我的一些算法。我錯過了幾種正確的組合，這是因爲我一回到成本超過15.05就回來了 - 我並沒有打算檢查可以添加的其他（便宜的）物品。這是我的新算法：

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

輸出：

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 

我想這可能都正確的組合，但我的問題依然存在：有沒有更好的算法？

Answer 4

現在你已經得到了所有正確的組合，但是你仍然在檢查比你需要的更多的東西（正如你的結果顯示的許多變化所證明的那樣）。另外，你忽略了最後一個擊中15.05分的項目。

我有一個PHP版本，執行遞歸調用的209次迭代（如果我得到所有的排列，它的確會是2012年）。如果在循環結束之前您可以減少計數，則可以取出剛剛檢查的項目。

我不知道CF的語法，但它會是這樣的：

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

編輯：供參考，這是我的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; 
?> 

輸出

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

編輯2：

由於解釋了爲什麼可以刪除元素需要比我可以放入評論更多一點，所以我在這裏添加它。

基本上，每個遞歸都會找到包含當前搜索元素的所有組合（例如，第一步將查找包括至少一個混合水果的所有內容）。理解它的最簡單方法是追蹤執行情況，但是由於這需要很大的空間，我會這樣做，就好像目標是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] 

在這一點上，我們已經檢查了包含任何混合水果的每種組合，因此不需要再次檢查混合水果。您也可以使用相同的邏輯在每個更深的遞歸中修剪數組。

像這樣追蹤它實際上意味着另一個小節省時間 - 知道價格從低到高排序意味着我們不需要在我們超過目標時繼續檢查項目。

Answer 5

下面是與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

是不是應該更多地飄逸着遞歸（在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)); 
     } 
    } 
} 

輸出

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

從@rcar's answer學習，以及稍後的另一個重構，我有以下。

與我編寫的很多東西一樣，我已經從CFML重構爲CFScript，但代碼基本相同。

我在數組中添加了一個動態起始點的建議（而不是按值傳遞數組並改變它的值用於未來遞歸），這使我得到了相同的統計數據（209次遞歸，571個組合價格檢查（循環迭代）），然後通過假設數組按照成本進行排序 - 因爲它是 - 並在我們超過目標價格時立即中斷。隨着中斷，我們下降到209次遞歸和376次循環迭代。

該算法還可以進行其他改進嗎？

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

即使揹包是NP完全性，這是一個非常特殊的問題：它通常的動態程序實際上是優秀（http://en.wikipedia.org/wiki/Knapsack_problem）

如果你這樣做了正確的分析，事實證明，它是O（nW），n是項目數量，W是目標數量。問題是當你必須在大W上進行DP時，那就是當我們得到NP行爲時。但是大多數情況下，揹包的表現相當好，你可以毫無問題地解決真正大的問題。就NP完全問題而言，揹包是最容易的問題之一。

Answer 9

它給出瞭解決方案的所有排列，但我認爲我擊敗了其他人的代碼大小。

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

解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 

Answer 10

下面是使用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}] 

因此該解決方案是訂購採樣板，混合水果，和2個數量級的溶液炎熱的翅膀，或訂購7個混合水果。

Answer 11

我想提出一個建議，關於算法本身的設計（這是我如何解釋你原來的問題）的意圖。這是我寫的解決方案的片段：

.... 

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

... 

（注意構造通過提高價格，使恆定時間提前終止時的餘額小於做排序菜單項。任何剩餘的菜單項）

的輸出爲一個樣品運行是：

7 mixed fruit (1505) = 1505 
1 mixed fruit (215) + 2 hot wings (710) + 1 sampler plate (580) = 1505 
348 calls, 347 loops, 79 falls 

設計建議我想強調的是，在上述C ode，findAndReportSolution(...)的每個嵌套（遞歸）調用處理恰好一個菜單項的數量，由index參數標識。換句話說，遞歸嵌套與一組嵌套循環的行爲相平行;最外面的計數可能使用第一個菜單項，下一個計算第二個菜單項的使用等等（當然，使用遞歸釋放代碼依賴於特定數目的菜單項！）

我認爲，這使得它更容易設計的代碼，更容易瞭解，每個調用都在做（佔一個特定項目的所有可能的用途，委派菜單下級呼叫的其餘部分）。它還避免了產生多項目解決方案的所有安排的組合式爆炸（如在上述輸出的第二行中那樣，其僅出現一次，而不是以不同順序的項目重複）。

我儘量讓代碼「顯而易見」，而不是試圖減少一些具體的方法調用的次數。例如，上述設計允許委託調用確定是否已達到解決方案，而不是繞過該調用點進行檢查，這會減少打擾代碼的代價，從而減少調用次數。

Answer 12

嗯，你知道什麼是奇怪的。解決方案是菜單上的第一個項目的七個。

因爲這顯然意味着要通過紙筆在很短的時間內解決，爲什麼不通過每個項目的價格除以訂單總額，看看一些機會，他們訂購一個項目的倍數？

例如，

15.05/2.15 = 7混合水果 15.05/2.75 = 5.5炸薯條。

然後轉移到簡單的組合...

15 /（2.15 + 2.75）= 3.06122449混合水果配薯條。

換句話說，假定溶液應該是由人簡單和可解不訪問計算機。然後測試最簡單，最明顯的（因此隱藏在明顯的視野中）解決方案的工作。

我發誓這個週末，當我在凌晨4:30次序$ 4.77值得開胃菜（含稅）的俱樂部關閉後，我拉這個在當地沙番。

Answer 13

以下是Clojure中的併發實現。爲了計算(items-with-price 15.05)需要大約14次組合代數遞歸和大約10次可能性檢查。花了大約6分鐘來計算我的英特爾Q9300上的(items-with-price 100)。

這隻給出第一個找到的答案，或者如果沒有，則爲nil，因爲這是所有問題的要求。爲什麼你會被告知需要做更多的工作;）？

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

在python中。
我有一些問題與「全局變量」，所以我把功能作爲一個對象的方法。這是遞歸調用本身29倍的漫畫的問題，在第一次成功匹配停止

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 

輸出：

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

如果你想要一個優化的算法，這是最好的嘗試價格按降序排列。這可以讓你先用盡剩餘量，然後看看剩餘量可以如何填充。

此外，您可以使用數學計算每次啓動每個食物的最大數量，所以你不用不會嘗試超過15.05美元目標的組合。

這種算法只需要嘗試88個組合，以獲得一個完整的答案，看起來就像是到目前爲止已經發布最低：

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

這裏展示兩種解決方案輸出：

 
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