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

我不认为这是人们能想到的最好/最具声明性的解决方案。有人有任何改进建议吗？提前致谢！

Answer 1

既然你提到了 SWI-Prolog 为什么不

?- use_module(library(clpfd)).

和 library( 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].

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 中，我缩短了一些变量/参数名称，并为累加器参数使用了一个有点搞笑的名称。我检查累加器不超过所需 Total 的方式使用了对 Between/3 的原始调用，但使用了计算出的上限而不是常量。在我的机器上，它将运行时间从几分钟缩短到几秒钟。

补充：我应该在这里提到我在上面的评论中所说的内容，菜单项现在按从最贵到最便宜的顺序排列。使用 SWI-Prolog 的 time/1 谓词表明，这将工作量从 1,923 次推理减少到 1,070 次推理。主要的改进（速度）来自于对 A 使用计算边界，而不是对每个项目使用 0 到 10 的范围。

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

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

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.