NP-full backpack

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 this is the best / most declarative solution you can come up with. Anyone have any suggestions for improvement? Thanks in advance!

Answer 1

Your approach based on generation and testing should be clear to any Prolog programmer with more than a few days of experience. Here are some minor tricks:

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

I changed go / 0 to go / 1 so that the Prolog engine cancels and releases all the solutions (there are two of them). The call to length / 2 may be omitted because totalCost / 4 does the work on the construction list. Amounts are equal in length with prices. I used write / 1 and nl / 0 to make it a little more portable.

In totalCost / 4, I abbreviated some variable / argument names and pampered a somewhat weak name for the battery argument. The way I checked that our battery does not exceed the desired Total uses your original call between / 3 , but with a calculated upper bound instead of a constant. On my machine, this reduced the runtime from minutes to several seconds.

Added: I have to mention here what was said in my comment above that the menu items are now ordered from the most expensive to the smallest. Using the predicate SWI-Prolog time / 1 shows that this reduces the work from 1923 pins to 1,070 pins. The main improvement (in speed) comes from the use of calculated boundaries on A, and not from 0 to 10 for each element.

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

Pay attention to the additional parentheses around the common target, as otherwise SWI-Prolog considers that we call the undefined time / 2 predicate.

Answer 2

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 indicating this, all the variables in the Amounts list are in the final range. Therefore, there is no need to "do the math" for the upper bound (which is often wrong in any case). To see specific solutions, marking / 2 is required:

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