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