 # Minimum Coin Problem #3

Apr 23rd, 2013
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /* problem 3. Giving away maximum weight of coins
2. http://www.takingthefun.com/2013/04/john-graham-cunnings-minimum-coin.html
3. Uses GNU Linear Programming Kit (glpk):
4. glpsol -m prob3.txt -o /dev/fd/1 | egrep 'Objective|used\['
5. */
6.
7.
8. set COIN;
9. param onhand {i in COIN} >= 0, integer; /* number of each coin on hand */
10. param weight {i in COIN} >= 0, integer; /* weight of each coin in centigrams */
11. var used {i in COIN} >= 0, integer; /* number of each coin used in solution */
12. param target integer;
13. maximize weightofcoins: sum{c in COIN} used[c] * weight[c];
14. s.t. valid{c in COIN}: used[c] <= onhand[c];
15. s.t. total: sum{c in COIN} c * used[c] >= target;
16. s.t. totalminusonecoin {d in COIN}: (sum{c in COIN} c * used[c]) - d <= target - 1;
17.
18. data;
19. param target := 170;
20. set COIN := 200 100 50 20 10 5 2 1;
21. param onhand :=
22. 200 1
23. 100 2
24. 50 2
25. 20 3
26. 10 1
27. 5 2
28. 2 2
29. 1 2;
30.
31. param weight :=
32. 200 1200
33. 100 950
34. 50 800
35. 20 500
36. 10 650
37. 5 325
38. 2 713
39. 1 356;
40.
41. end;