10

我看到了这个XKCD 漫画中提到的问题的 ECLiPSe 解决方案。我试图将其转换为纯 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).

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

4

2 回答 2

6

既然你提到 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].
于 2011-06-07T14:43:59.747 回答
5

任何拥有几天以上经验的 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 的工作，使其长度与价格相等。我使用write/1和nl/0使其更便携。

在totalCost/4中，我缩短了一些变量/参数的名称，并为 accumulator 参数使用了一个有点搞笑的名称。我强加检查我们的累加器不超过所需 Total 的方式使用您对between/3的原始调用，但使用计算的上限而不是常数。在我的机器上，它将运行时间从几分钟缩短到几秒钟。

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

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

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

于 2011-06-06T17:41:15.487 回答