在XKCD中解决NP完全问题

Question

在XKCD中解决NP完全问题

45

通用解决方案可以让你得到50%的小费

我不确定这是否是最好的方法，但这是我目前想出来的。我正在使用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份混合水果，而完成测试组合函数需要执行232次。

是否有更好的算法可以得出正确的解决方案？我是否已经得出了正确的解决方案？

- Adam Tuttle

93

那种语言真是糟糕透了，就好像 VB 和 XML 生下了一个孩子。 - Paul Batum

8

"有没有更好的算法能够得出正确的解决方案？"这是计算机科学中最伟大的未解之谜之一！如果stackoverflow能提供一个通用解决方案，我会非常印象深刻 :)。" - HenryR

12

两个私生子的私生子。+1 保罗·巴图姆。 - yfeldblum

1

@Paul Batum：这让我开怀大笑。我的感受完全一样。 - Noldorin

1

有一种语言实际上看起来像那样吗？呕吐 - Peter C

显示剩余6条评论

15个回答

24

NP完全问题的关键不在于它在小数据集上很棘手，而是解决它所需的工作量以大于多项式的速度增长，即没有O(n^x)算法。

如果时间复杂度是O(n!)，如上述两个问题中的（我相信），那就是NP问题。

- MarkR

10

递归方式（在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

- Sklivvz

3

除了将相同的答案列出9次以外，请只返回翻译后的文本。 - Stimy

你需要在计算答案后添加一个排序，以便去除重复项。 - Mark Allanson

7

比 PROLOG 的三行代码更优雅？你在开玩笑吗？ - Piotr Dobrogost

修复它以显示实际订单（而不是值！），你就会得到投票支持！ - elcuco

7

即使背包问题是 NP 完全的，但它是一个非常特殊的问题：对于它通常的动态规划实际上是非常优秀的（http://en.wikipedia.org/wiki/Knapsack_problem）。如果你进行正确的分析，就会发现它是 O(nW) 的，其中 n 是物品数量，W 是目标数。问题在于当您需要 DP 大量的 W 时，这时我们会得到 NP 行为。但在大多数情况下，背包问题表现得相当良好，您可以轻松地解决它的大型实例。就 NP 完全问题而言，背包问题是最简单的之一。

- Ying Xiao

1

这个特定版本还可以简化为O(n * lcm(numbers))。如果你的背包相当不错，那么它可能小于W。 - FryGuy

4

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

因此，解决方案是订购一个“样品盘”，一份混合水果和两份热翅膀，或者订购七份混合水果。

- Jeremy Zucker

3

以下是使用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,
*)

- Brian

2

了解背包问题。

- Adam Rosenfield

1

这是一个不同的问题，背包问题假设非精确解决方案，并且没有重复选择。 - Sklivvz

那么，为什么餐厅顾客会向服务员提供关于背包问题的文章呢？ - Windows programmer

2

可能是因为它是一部卡通片。 - Jasper Bekkers

2

因为这两个问题密切相关，解决背包问题也将解决这个问题。 - jalf

2

我对算法设计本身提出一个建议（这是我理解你原来问题的意图）。这是我写的解决方案的一部分：

....

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

我想要强调的设计建议是，在上述代码中，每个嵌套（递归）调用findAndReportSolution(...)都处理了一个菜单项的数量，由index参数确定。换句话说，递归嵌套与内联嵌套循环的行为相似；最外层计算第一个菜单项的可能使用次数，下一层计算第二个菜单项的使用次数，以此类推。（当然，递归的使用使得代码不再依赖于特定数量的菜单项！）

我建议这样做可以更容易地设计代码，并且更容易理解每个调用正在执行的操作（考虑特定项目的所有可能使用情况，将剩余的菜单委托给下级调用）。它还避免了产生多项解决方案的组合爆炸（如上面输出的第二行只出现一次，而不是重复出现不同顺序的项目）。

我试图最大化代码的“显而易见性”，而不是尝试最小化某些特定方法的调用次数。例如，上述设计让一个委托调用确定是否已经找到解决方案，而不是在调用点周围包装该检查，这会减少调用次数，但会使代码变得混乱。

- joel.neely

2

你现在已经有了所有正确的组合，但是你仍然检查了比你需要的更多（正如你的结果所显示的那样，有很多排列组合）。此外，你忽略了最后一个达到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]

目前为止，我们已经检查了包含任何混合水果的所有组合，因此无需再次检查混合水果。您可以在每个更深的递归中使用相同的逻辑来修剪数组。

像这样跟踪实际上提出了另一个轻微的时间节省方法--知道价格是从低到高排序的意味着一旦超过目标，我们就不需要继续检查物品。

- rcar

我不确定为什么你可以从数组中删除该项。在这种情况下，对我来说似乎没问题，但并不一定适用于所有情况。你能再解释一下吗？ - Adam Tuttle

好的，我现在明白删除元素是如何有帮助的了。看起来你是通过值传递而不是引用传递（有效地）。这是真的吗？我一直在通过引用传递来保留内存并降低运行时间，但更少的递归可能会使通过值传递与删除操作获胜（我会计时来确认）。 - Adam Tuttle

是的，你说得对，本质上它是按值传递（我有点懒）。你可以通过向递归函数传递要检查的最小索引而不是修改后的数组来改进它。 - Randy

1

嗯，你知道什么很奇怪吗？解决方案是菜单上第一项的七倍。

既然显然是要在短时间内用纸和笔解决，为什么不将订单总额除以每个项目的价格，看看是否有可能他们订购了同一种物品的多个数量呢？

例如，

15.05/2.15 = 7份水果沙拉 15.05/2.75 = 5.5份薯条。

然后继续尝试简单的组合...

15 / (2.15 + 2.75) = 3.06122449份混合水果沙拉和薯条。

换句话说，假设解决方案应该是简单的，并且可以由没有计算机访问权限的人类解决。然后测试最简单、最明显（因此隐藏在眼前）的解决方案是否有效。

我发誓这周末在当地的餐馆点$4.77的开胃菜（包括税）在凌晨4:30关门后。

- Krystine

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Toby · Accepted Answer

它给出了所有解的排列，但我认为我在代码大小方面领先于其他人。

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