Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #define INF (1 << 29)
- using namespace std;
- int CoinChange(vector <int> coins, int maxValor)
- {
- vector <int> T(maxValor+1, INF);
- vector <int> C(maxValor+1, INF);
- T[0] = 0; ///Hardcodeado
- for(int j=0; j<coins.size(); j++)
- {
- for(int i=coins[j]; i<=maxValor; i++)
- {
- if(T[i] > T[i-coins[j] ] + 1)
- {
- T[i] = T[i-coins[j] ] + 1;
- C[i] = j;
- }
- }
- }
- cout << "Monedas utilizadas: ";
- int pos = maxValor;
- while(C[pos] != INF)
- {
- cout << coins[C[pos]] << " ";
- pos = pos - coins[C[pos]];
- }
- return T[maxValor];
- }
- int main()
- {
- cout << CoinChange({7, 2, 3, 6}, 13) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment