david12457899

minimizing coins

May 13th, 2021
549
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "bits/stdc++.h"
  2.  
  3. const int max = 1000000007;
  4.  
  5.  
  6.  
  7. int main()
  8. {
  9.     int n, x;
  10.     std::cin >> n >> x;
  11.  
  12.     std::vector<int> coins(n);
  13.     std::vector<int> numebrOfCoins(x + 1, 1000000000);
  14.  
  15.     for (int i = 0; i < n; i++)
  16.     {
  17.         std::cin >> coins[i];
  18.     }
  19.  
  20.     numebrOfCoins[0] = 0;
  21.  
  22.     for (int value = 1; value <= x; value++)
  23.     {
  24.         for (int j = 0; j < n; j++)
  25.         {
  26.             if (value - coins[j] >= 0)
  27.             {
  28.                 numebrOfCoins[value] = std::min(numebrOfCoins[value], numebrOfCoins[value - coins[j]] + 1);
  29.             }
  30.         }
  31.        
  32.     }
  33.  
  34.     if (numebrOfCoins[x] != 1000000000)
  35.     {
  36.         std::cout << numebrOfCoins[x];
  37.     }
  38.     else
  39.     {
  40.         std::cout << -1;
  41.     }
  42.    
  43.  
  44.     return 0;
  45. }
RAW Paste Data