解决XKCD中的NP完全问题
有问题的问题/漫画： 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个执行才能完成。
有没有更好的algorithm来find正确的解决scheme？ 我有没有find正确的解决scheme？
关于一个NP完全问题的观点并不是说它在小数据集上是棘手的，而是解决它的工作量以大于多项式的速率增长，即没有O（n ^ x）algorithm。
如果时间复杂度是O（n！），如（我相信）上面提到的两个问题，那就是NP。
它给出了解决scheme的所有排列，但我认为我击败了其他人的代码大小。
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解决scheme：
?- 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
recursion（在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
即使背包是NP完成，这是一个非常特殊的问题：通常的dynamic程序，事实上是非常好的（ http://en.wikipedia.org/wiki/Knapsack_problem ）
如果你做了正确的分析，结果是O（nW），n是项目数量，W是目标数量。 问题是，当你必须在一个大W的DP，这是当我们得到NP的行为。 但是大多数情况下，背包的performance相当好，你可以毫无问题地解决大量的背包问题。 就NP完全问题而言，背包是最简单的一个。
这是使用constraint.py的解决scheme
>>> 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个混合水果。
以下是F＃的解决scheme：
#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, *)
阅读背包问题 。
你现在已经有了所有正确的组合，但是你仍然要检查比你需要的更多的东西（正如你的结果显示的许多变化所certificate的那样）。 另外，你省略了最后一个击中15.05分的项目。
我有一个PHP版本，做了recursion调用的209次迭代（2012年，如果我得到所有的排列）。 你可以减less你的数量，如果在你的循环结束之前，你拉出你刚刚检查的项目。
我不知道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：
既然解释了为什么你可以删除元素将需要比我可以在评论中多一点，我在这里添加它。
基本上，每个recursion都会find包含当前search元素的所有组合（例如，第一步将会find包括至less一个混合果实的所有内容）。 理解它的最简单的方法是追踪执行，但是由于这将占用大量的空间，所以我会这样做，就好像目标是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]
在这一点上，我们已经检查了包含任何混合水果的每种组合，所以不需要再次检查混合水果。 您也可以使用相同的逻辑在每个更深的recursion中修剪数组。
通过这样的追踪，实际上意味着又一次节省时间 – 知道价格是从低到高的sorting意味着我们不需要一旦检查目标就检查项目。
我会提出一个有关algorithm本身devise的build议（这就是我如何解释原始问题的意图）。 这是我写的解决scheme的一个片段 ：
.... 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); } ...
（请注意，构造函数通过提高价格来对菜单项进行sorting，以在剩余余额小于任何剩余菜单项时启用恒定时间提前终止。
样品运行的输出是：
7 mixed fruit (1505) = 1505 1 mixed fruit (215) + 2 hot wings (710) + 1 sampler plate (580) = 1505 348 calls, 347 loops, 79 falls
我想强调的devisebuild议是，在上面的代码中， findAndReportSolution(...)每个嵌套（recursion）调用处理由index参数标识的恰好一个菜单项的数量。 换句话说，recursion嵌套与一组嵌套循环的行为是平行的; 第一个菜单项的可能使用的最外面的计数，第二个菜单项的使用计数的下一个等等（当然，使用recursion解放代码依赖于特定数目的菜单项！）
我build议这样可以更容易地devise代码，并且更容易理解每个调用正在做什么（考虑特定项目的所有可能用途，将菜单的其余部分委托给从属调用）。 它还避免了产生多项目解决scheme的所有安排的组合式爆炸（如在上述输出的第二行中那样，只发生一次，而不是以不同顺序的项目重复）。
我试图最大化代码的“明显性”，而不是尽量减less某些特定方法的调用次数。 例如，上面的devise让一个委托调用来决定是否已经达到了一个解决scheme，而不是围绕着这个调用点来包装这个检查，这会减less代码混乱的代价。
嗯，你知道什么是奇怪的。 解决scheme是菜单上的第一个项目的七个。
既然这显然是要在短时间内用纸和铅笔来解决的，那么为什么不把订单总额除以每件商品的价格，看看是否有机会订购一件商品的倍数？
例如，
15.05 / 2.15 = 7混合水果15.05 / 2.75 = 5.5薯条。
然后继续简单的组合…
15 /（2.15 + 2.75）= 3.06122449混合水果和薯条。
换句话说，假设解决scheme应该是简单的，并且可以由人类解决而不需要访问计算机。 然后testing是否最简单，最明显的（因此隐藏在明显的）解决scheme（s）工作。
我发誓我在本周末在当地的科尼举办了这场比赛，当时我在俱乐部closures后的凌晨4:30点了4.77美元的开胃菜（含税）。
在python中。
我有一些“全局variables”的问题，所以我把这个函数作为一个对象的方法。 它是recursion的，它在漫画中自动调用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(pi, 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 '%dx %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
实际上，我已经重构了一些algorithm。 我错过了几个正确的组合，这是因为我一回到成本超过15.05就回来了 – 我并没有去检查可以添加的其他（便宜的）物品。 这是我的新algorithm：
<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
我认为这可能有所有正确的组合，但我的问题依然存在：是否有更好的algorithm？
从rcar的回答中学习，以及后来的另一个重构，我有以下几点。
与我编写的很多东西一样，我已经从CFML重构为CFScript，但代码基本相同。
我在数组中join了一个dynamic的起始点（而不是按值传递数组，并为未来的recursion改变它的值），这使我得到了相同的数据（209次recursion，571次组合价格检查（循环迭代）），然后通过假定数组按照成本进行sorting – 因为它是 – 并在我们超过目标价格时立即中断。 随着中断，我们下降到209recursion和376循环迭代。
该algorithm还有哪些其他的改进？
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#");
这是Clojure中的并发实现。 计算(items-with-price 15.05)需要大约14次组合代recursion和大约10次可能性检查。 花了我6分钟计算(items-with-price 100)在我的英特尔Q9300。
这只给出了第一个find的答案，或者如果没有，那么这是所有问题的要求。 你为什么要做更多的工作呢？）？
;; 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))
如果你想要一个优化的algorithm，最好以降序的方式尝试价格。 这可以让你用尽剩余数量，然后看看其余的数据是如何填充的。
此外，您可以使用math计算出每次开始食物的最大数量，因此您不要尝试超过15.05美元的组合。
这个algorithm只需要尝试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); } }
以下是显示两种解决scheme的输出：
9尝试：1 * 580 + 0 * 420 + 2 * 355 + 0 * 335 + 0 * 275 + 1 * 215 88尝试：0 * 580 + 0 * 420 + 0 * 355 + 0 * 335 + 0 * 275 + 7 * 215 组合尝试：88
