• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Minimum Coin Problem #1

kh444n Apr 23rd, 2013 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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;
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top