farhin_khaled

Coin Change

Dec 1st, 2021 (edited)
409
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define ull unsigned long long int
  4. #define pb push_back
  5. #define mp make_pair
  6. #define in insert
  7. #define f first
  8. #define sc second
  9. #define M 1000005
  10. #define MAX 10000000
  11. #define inf 1000000
  12. using namespace std;
  13.  
  14. int main()
  15. {
  16.   int n,tt;
  17.   cin >> n >> tt;
  18.   int coins[n];
  19.   for(int i=1;i<=n;i++) cin >> coins[i];
  20.   sort(coins,coins+(n+1));
  21.   int k[n+2][tt+2];
  22.   for(int i=0;i<=n;i++)
  23.   {
  24.     for(int w=0;w<=tt;w++)
  25.     {
  26.       if(i==0) k[i][w] = inf;
  27.       else if(w==0) k[i][w] = 0;
  28.       else if(coins[i]>w) k[i][w] = k[i-1][w];
  29.       else k[i][w] = min(k[i-1][w],1+k[i][w-coins[i]]);
  30.     }
  31.   }
  32.  
  33.   int temp_tt = tt;
  34.   for(int i=n;i>=1 && temp_tt;i--)
  35.   {
  36.     for(int w=temp_tt;w>=1 && temp_tt;w--)
  37.     {
  38.       if(k[i][w]==k[i-1][w]) continue;
  39.       else
  40.       {
  41.         w = w-coins[i];
  42.         temp_tt -= coins[i];
  43.         cout << "coin = " << coins[i] << endl;
  44.       }
  45.     }  
  46.   }
  47.   cout << k[n][tt] << endl;
  48.  
  49.   return 0;
  50. }
  51.  
  52.  
RAW Paste Data