NP完全的背包问题

Question

我看到了这个 ECLiPSe解决方案，它可以解决这个 XKCD漫画中提到的问题。我试图将其转换为纯Prolog。

go:-
    Total = 1505,
    Prices = [215, 275, 335, 355, 420, 580],
    length(Prices, N),
    length(Amounts, N),
    totalCost(Prices, Amounts, 0, Total),
    writeln(Total).

totalCost([], [], TotalSoFar, TotalSoFar).
totalCost([P|Prices], [A|Amounts], TotalSoFar, EndTotal):-
    between(0, 10, A),
    Cost is P*A,
    TotalSoFar1 is TotalSoFar + Cost,
    totalCost(Prices, Amounts, TotalSoFar1, EndTotal).

我认为这不是最好/最声明式的解决方案。有没有人有改进的建议？谢谢！

- Ashley

---

从最昂贵的物品开始逆向工作似乎是有效的，因为这些物品允许从预算/背包中减去较小的金额倍数（减少分支）。对您现有代码的简单修改是检查TotalSoFar是否小于或等于EndTotal。在纸上尝试中，我很快就找到了一个解决方案。 - hardmath

Answer 1

既然您提到SWI-Prolog，为什么不考虑使用它呢？

?- use_module(library(clpfd)).

并且使用lambda库。

?- Total = 1505, Prices = [215, 275, 335, 355, 420, 580],
      maplist(\P^A^M^(P*A #= M, A #>=0),Prices,Amounts,Ms),
      sum(Ms, #=, Total).

通过这种方式，列表Amounts中的所有变量都在有限的范围内。因此，没有必要“做数学运算”以获得上界（通常会出错）。 为了看到具体的解决方案，需要使用labeling/2函数：

?- Total = 1505, Prices = [215, 275, 335, 355, 420, 580],
      maplist(\P^A^M^(P*A #= M, A #>=0),Prices,Amounts,Ms),
      sum(Ms, #=, Total),
      labeling([], Amounts).
   Total = 1505, Prices = [215,275,335,355,420,580],
   Amounts = [1,0,0,2,0,1], Ms = [215,0,0,710,0,580]
;  Total = 1505, Prices = [215,275,335,355,420,580],
   Amounts = [7,0,0,0,0,0], Ms = [1505,0,0,0,0,0].

- false

Answer 2

你的生成-测试方法应该对拥有几天经验的任何Prolog程序员都是易懂的。以下是一些小的调整：

go(Amounts) :-
    Prices = [580, 420, 355, 335, 275, 215],
    totalCost(Prices, Amounts, 0, 1505),
    write(Amounts), nl.

totalCost([], [], Total, Total).
totalCost([P|Prices], [A|Amounts], SoFar, Total):-
    Upper is (Total-SoFar)//P,
    between(0,Upper,A),
    SoNear is SoFar + P*A,
    totalCost(Prices, Amounts, SoNear, Total).

我将 go/0 改为 go/1，这样 Prolog 引擎就可以回溯并产生所有解决方案（共两个）。调用 length/2 可以省略，因为 totalCost/4 已经完成了构建 Amounts 列表与 Prices 相等长度的工作。我使用了 write/1 和 nl/0 使它更加通用。

在 totalCost/4 中，我缩短了一些变量/参数名称，并为累加器参数取了一个略带玩笑的名称。我通过使用计算得出的上界而不是常数来实现检查累加器是否超过所需总和的方式来强制执行检查。在我的机器上，它将运行时间从几分钟缩短到几秒钟。 添加： 我应该在这里提到我在上面的评论中说过的，即菜单项目现在按价格从高到低排序。使用 SWI-Prolog 的 time/1 谓词可以看出，这将工作量从 1,923 推至 1,070 次推理。主要改进（在速度上）来自于对每个项目使用计算边界而不是范围为 0 到 10。

time((go(A),false)).

请注意，复合目标周围有额外的括号，否则SWI-Prolog会认为我们调用未定义的time/2谓词。

- hardmath

Answer 3

可以简单地表达为 clpBNR：

go :-
    Amounts = [A,B,C,D,E,F],
    Amounts::integer(0, _),
    { (A*215) + (B*275) + (C*335) + (D*355) + (E*420) + (F*580) == 1505 },
    solve(Amounts),
    writeln(Amounts).

在 SWI-Prolog 中的结果：

?- time(go).
[1,0,0,2,0,1]
% 35,063 inferences, 0.014 CPU in 0.014 seconds (99% CPU, 2483361 Lips)
true ;
[7,0,0,0,0,0]
% 50,954 inferences, 0.023 CPU in 0.023 seconds (100% CPU, 2262260 Lips)
true.

- brebs