GastonFontenla

Coin Change OIA

Oct 16th, 2016
145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. #define INF (1 << 29)
  5.  
  6. using namespace std;
  7.  
  8. int CoinChange(vector <int> coins, int maxValor)
  9. {
  10.     vector <int> T(maxValor+1, INF);
  11.     vector <int> C(maxValor+1, INF);
  12.     T[0] = 0; ///Hardcodeado
  13.  
  14.     for(int j=0; j<coins.size(); j++)
  15.     {
  16.         for(int i=coins[j]; i<=maxValor; i++)
  17.         {
  18.             if(T[i] > T[i-coins[j] ] + 1)
  19.             {
  20.                 T[i] = T[i-coins[j] ] + 1;
  21.                 C[i] = j;
  22.             }
  23.         }
  24.     }
  25.  
  26.     cout << "Monedas utilizadas: ";
  27.     int pos = maxValor;
  28.  
  29.     while(C[pos] != INF)
  30.     {
  31.         cout << coins[C[pos]] << " ";
  32.         pos = pos - coins[C[pos]];
  33.     }
  34.  
  35.     return T[maxValor];
  36. }
  37.  
  38. int main()
  39. {
  40.     cout << CoinChange({7, 2, 3, 6}, 13) << endl;
  41.     return 0;
  42. }
Advertisement
Add Comment
Please, Sign In to add comment