NP-complete背包

Question

我看到这个日食的解决方案中提到的问题这个 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中的所有变量都在有限范围内.所以没有必要为上限"做数学"(这通常会出错).要查看具体的解决方案,需要标记/ 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更改为/ 1,以便Prolog引擎将回溯并生成所有解决方案(有两个).对length/2的调用可以省略,因为totalCost/4使构建列表Amounts的工作具有与Price相等的长度.我使用write/1和nl/0使它更具可移植性.

在totalCost/4中,我缩短了一些变量/参数名称,并沉迷于累加器参数的略微jokey名称.我强制检查我们的累加器不超过所需的总计的方式使用原始调用在/ 3之间但是使用计算的上限而不是常量.在我的机器上,它将运行时间从几分钟缩短到几秒钟.

补充:我应该在这里提一下上面的评论中说的菜单项目现在从最昂贵到最少订购.使用SWI-Prolog的时间/ 1谓词表明,这将工作从1,923个推论减少到1,070个推论.主要改进(速度)来自于使用A上的计算边界而不是每个项目的范围0到10.

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

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