Advertisement
kh444n

Minimum Coin Problem #1

Apr 23rd, 2013
205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.71 KB | None | 0 0
  1. /* problem 1. giving away a maximum number of coins with the exact amount
  2. http://www.takingthefun.com/2013/04/john-graham-cunnings-minimum-coin.html
  3. Uses GNU Linear Programming Kit (glpk):
  4. glpsol -m prob1.txt -o /dev/fd/1 | egrep 'Objective|used\['
  5. */
  6.  
  7. set COIN;
  8. param onhand {i in COIN} >= 0, integer; /* number of each coin on hand */
  9. var used {i in COIN} >= 0, integer; /* number of each coin used in solution */
  10. param target integer;
  11. maximize ncoinsused: sum{c in COIN} used[c];
  12. s.t. valid{c in COIN}: used[c] <= onhand[c];
  13. s.t. total: sum{c in COIN} c * used[c] = target;
  14.  
  15. data;
  16. param target := 170;
  17. set COIN := 200 100 50 20 10 5 2 1;
  18. param onhand :=
  19. 200 1
  20. 100 2
  21. 50 2
  22. 20 3
  23. 10 1
  24. 5 2
  25. 2 2
  26. 1 2;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement