fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.     int n, m;
  7.     cin>>n>>m;
  8.     int coin[n];
  9.     for(int i = 0; i < n; i++)
  10.     {
  11.         cin>>coin[i];
  12.     }
  13.  
  14.     long long int dp_coin[n+1][m+1];
  15.  
  16.     for(int i = 0; i < n+1; i++)
  17.     {
  18.         dp_coin[i][0] = 0;
  19.     }
  20.     for(int j = 1; j < m+1; j++)
  21.     {
  22.         dp_coin[0][j] = INT_MAX;
  23.     }
  24.  
  25.     for(int i = 1; i < n+1; i++)
  26.     {
  27.         for(int j = 1; j < m+1; j++)
  28.         {
  29.             if(coin[i-1] > j)
  30.             {
  31.                 dp_coin[i][j] = dp_coin[i-1][j];
  32.             }
  33.             else
  34.             {
  35.                 dp_coin[i][j] = min(dp_coin[i-1][j], 1+dp_coin[i][j-coin[i-1]]);
  36.  
  37.             }
  38.         }
  39.     }
  40.  
  41.     for(int i = 0; i < n+1; i++)
  42.     {
  43.         for(int j = 0; j < m+1; j++)
  44.         {
  45.             cout<<dp_coin[i][j]<<" ";
  46.         }
  47.         cout<<endl;
  48.     }
  49.  
  50.  
  51.     int i = n, j = m;
  52.     while(i > 0)
  53.     {
  54.         while(dp_coin[i][j] != dp_coin[i-1][j])
  55.         {
  56.             cout<<coin[i-1]<<" is selected"<<endl;
  57.             j = j - coin[i-1];
  58.         }
  59.         i = i-1;
  60.     }
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71. }
  72.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
3 20
1 2 5
stdout
copy 
0 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 
0 1 1 2 2 1 2 2 3 3 2 3 3 4 4 3 4 4 5 5 4 
5 is selected
5 is selected
5 is selected
5 is selected
https://ideone.com/nQTStp
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!