inhuman_Arif

Coin change dp

Dec 1st, 2021
677
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. const int INF = 100000;
  7.  
  8. int coin_change(int coins[], int value, int k)
  9. {
  10.     int M[value+2];
  11.     M[0] = 0;
  12.  
  13.     int used[value+2];
  14.     used[0] = 0;
  15.  
  16.     for(int i=1;i<=value;i++)
  17.     {
  18.         int minimum = INF;
  19.         int coin=0;
  20.  
  21.         for(int j=0;j<=k;j++)
  22.         {
  23.             if(i >= coins[j])
  24.             {
  25.                 if((1+M[i-coins[j]]) < minimum)
  26.                 {
  27.                     minimum = 1+M[i-coins[j]];
  28.                     coin = j;
  29.                 }
  30.             }
  31.         }
  32.         M[i] = minimum;
  33.         used[i] = coin;
  34.     }
  35.  
  36.     int l = value;
  37.     while(l>0)
  38.     {
  39.         printf("%d\n",coins[used[l]]);
  40.         l-=coins[used[l]];
  41.     }
  42.     return M[value];
  43. }
  44.  
  45. int main()
  46. {
  47.     #ifndef ONLINE_JUDGE
  48.         freopen("input.txt", "r", stdin);
  49.         freopen("output.txt", "w", stdout);
  50.     #endif
  51.  
  52.     int n;
  53.     cin >> n;
  54.     int coins[n];
  55.     for(int i=0;i<n;i++)
  56.       cin >> coins[i];
  57.    
  58.     int value;
  59.     cin >> value;
  60.  
  61.     cout << coin_change(coins, value, n-1);
  62.  
  63.  
  64.     return 0;
  65. }
RAW Paste Data