Advertisement
kh444n

Minimum Coin Problem #3

Apr 23rd, 2013
224
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.96 KB | None | 0 0
  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;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement