NP-complete knapsack

Question

I saw this ECLiPSe solution to the problem mentioned in this XKCD comic. I tried to convert this to pure 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).

I don't think that this is the best / most declarative solution that one can come up with. Does anyone have any suggestions for improvement? Thanks in advance!

Answer 1

Since you mention SWI-Prolog why not

?- use_module(library(clpfd)).

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

By stating this, all variables in the list Amounts are in a finite range. So there is no need to "do the math" for an upper bound (which often goes wrong anyway). To see concrete solutions, labeling/2 is needed:

?- 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].