/*
Discount puzzle in Picat.
From Martin Chlond Integer Programming Puzzles:
http://www.chlond.demon.co.uk/puzzles/puzzles4.html, puzzle nr. 11.
Source: J. & L. Poniachik, Hard-to-Solve Brainteasers (p16), Sterling
"""
11. Nice Discounts
A bookstore has a nice discount policy. If you buy a $20 book today, you get a 2% discount
on your next purchase. If you buy a $15 book, you get a 1.5% discount on your next purchase.
That is, for each $10 you spend you get 1% discount on your next purchase. If you have to
buy three books that cost $10, $20 and $30, you could buy the $30 book today, the $10 book
tomorrow (on which you'll get a 3% discount), and the $20 book the following day (on which
you'll get a 1% discount). Or you could buy the $30 book and the $20 book today, and the
$10 book tomorrow (with a 5% discount). What is the cheapest way to buy five books priced at
$10, $20, $30, $40 and $50?
(Poniachek)
"""
This model was inspired by the AMPL model created by Martin Chlond.
http://www.chlond.demon.co.uk/puzzles/sol4s11.html
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
% nonlinear constraint
% import util.
import mip.
main => go.
go =>
Cost = [10, 20, 30, 40, 50],
M = 5,
X = new_array(M,M),
X :: 0..100,
T = new_list(M),
T :: 0..100,
TotCost #= sum(Cost) - sum([0.001*T[K-1]*T[K] : K in 2..M]),
foreach(J in 1..M)
T[J] #= sum([Cost[I]*X[I,J] : I in 1..M])
end,
foreach(I in 1..M)
sum([X[I,J] : J in 1..M]) #= 1
end,
solve($[min(TotCost)],X),
println(totCost=TotCost),
println(x=X),
nl.