NP-complete problem in Prolog
Posted
by
Ashley
on Stack Overflow
See other posts from Stack Overflow
or by Ashley
Published on 2011-06-06T14:28:10Z
Indexed on
2012/07/08
3:16 UTC
Read the original article
Hit count: 227
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!
© Stack Overflow or respective owner