# Coin Change

Dec 1st, 2021 (edited)
525
0
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.