# Untitled

By: a guest on May 1st, 2012  |  syntax: C++  |  size: 2.44 KB  |  hits: 25  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. #include <iostream>
2. #include <vector>
3. #include <map>
4. #include <algorithm>
5.
6. using namespace std;
7.
8. void makeChange(vector<int>, int price);
9. void optimalCoins(vector<int>, vector< vector<int> >, int, int);
10.
11. int main()
12. {
13.     int price, num, val;
14.     vector<int> mycoins;
15.
16.     mycoins.push_back(1);
17.
18.     cout << "A coin with a demonination of '1' has already been added. \n" << "How many coin values would you like to enter? ";
19.     cin >> num;
20.     cout << endl << "Please enter " << num << " coin values:\n";
21.
22.     // get input
23.     for (int index = 0; index < num; index++) {
24.         cin >> val;
25.         if (val != 1) {mycoins.push_back(val);}  // insert val into our vector of coins
26.     }
27.
28.
29.     cout << endl << "How many cents would you like change for? ";
30.     cin >> price;
31.
32.     sort(mycoins.begin(), mycoins.end()); // sort mycoins from smallest to largest value
33.
34.     makeChange(mycoins, price); // call the make change function using the mycoin vector and price given
35.
36. }
37.
38. /*
39.     This function creates a True/False matrix using multidimensional vectors
40.     to determine which coins will be used to create change in the most efficient
41.     way possible for the given amount.
42. */
43. void makeChange(vector<int> mycoins, int price)
44. {
45.     int amount;
46.     int n = mycoins.size() - 1;
47.     vector< vector<int> > min, used;
48.
49.     // initialize all previous amounts
50.     for (amount = 0; amount <= price; amount++) {
51.         min[n][amount] = amount;
52.         used[n][amount] = true;
53.     }
54.
55.     for (int index = n - 1; n >= 1; n--) {
56.
57.         for (amount = 0; amount <= price; amount++) {
58.
59.             if (mycoins[index] > amount || min[index+1][amount] < 1 + min[index][amount - mycoins[index]]) {
60.                 min[index][amount] = min[index+1][amount];
61.                 used[index][amount] = false;
62.             }
63.
64.             else {
65.                 min[index][amount] = 1 + min[index][amount - mycoins[index]];
66.                 used[index][amount] = true;
67.             }
68.         }
69.     }
70.
71.     optimalCoins(mycoins, used, 0, price);
72.
73. }
74.
75. void optimalCoins(vector<int> mycoins, vector< vector<int> > used, int index, int amount) {
76.
77.     if (amount == 0)
78.         return;
79.
80.     if (used[index][amount]) {
81.         cout << "Coin of Denomination " << mycoins[index] << " used.\n";
82.         optimalCoins(mycoins, used, index + 1, amount - mycoins[index]);
83.     }
84.
85.     else {
86.         optimalCoins(mycoins, used, index + 1, amount);
87.     }
88. }