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.     long long int dp_coin[n+1][m+1];
  14.  
  15.     for(int i = 0; i < n+1; i++)
  16.     {
  17.         dp_coin[i][0] = 0;
  18.     }
  19.     for(int j = 1; j < m+1; j++)
  20.     {
  21.         dp_coin[0][j] = INT_MAX;
  22.     }
  23.  
  24.     for(int i = 1; i < n+1; i++)
  25.     {
  26.         for(int j = 1; j < m+1; j++)
  27.         {
  28.             if(coin[i-1] > j)
  29.             {
  30.                 dp_coin[i][j] = dp_coin[i-1][j];
  31.             }
  32.             else
  33.             {
  34.                 dp_coin[i][j] = min(dp_coin[i-1][j], 1+dp_coin[i][j-coin[i-1]]);
  35.             }
  36.         }
  37.     }
  38.  
  39.     for(int i = 0; i < n+1; i++)
  40.     {
  41.         for(int j = 0; j < m+1; j++)
  42.         {
  43.             cout<<dp_coin[i][j]<<" ";
  44.         }
  45.         cout<<endl;
  46.     }
  47.  
  48.  
  49.     int i = n, j = m;
  50.     while(i > 0)
  51.     {
  52.         while(dp_coin[i][j] != dp_coin[i-1][j])
  53.         {
  54.             j = j-coin[i-1];
  55.             cout<<coin[i-1]<<" is selected"<<endl;
  56.             continue;
  57.         }
  58.         i = i-1;
  59.  
  60.     }
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74. }
  75.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
6 99
1 3 4 6 8 11
stdout
copy 
0 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 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 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 
0 1 2 1 2 3 2 3 4 3 4 5 4 5 6 5 6 7 6 7 8 7 8 9 8 9 10 9 10 11 10 11 12 11 12 13 12 13 14 13 14 15 14 15 16 15 16 17 16 17 18 17 18 19 18 19 20 19 20 21 20 21 22 21 22 23 22 23 24 23 24 25 24 25 26 25 26 27 26 27 28 27 28 29 28 29 30 29 30 31 30 31 32 31 32 33 32 33 34 33 
0 1 2 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 10 10 10 10 11 11 11 11 12 12 12 12 13 13 13 13 14 14 14 14 15 15 15 15 16 16 16 16 17 17 17 17 18 18 18 18 19 19 19 19 20 20 20 20 21 21 21 21 22 22 22 22 23 23 23 23 24 24 24 24 25 25 25 
0 1 2 1 1 2 1 2 2 2 2 3 2 3 3 3 3 4 3 4 4 4 4 5 4 5 5 5 5 6 5 6 6 6 6 7 6 7 7 7 7 8 7 8 8 8 8 9 8 9 9 9 9 10 9 10 10 10 10 11 10 11 11 11 11 12 11 12 12 12 12 13 12 13 13 13 13 14 13 14 14 14 14 15 14 15 15 15 15 16 15 16 16 16 16 17 16 17 17 17 
0 1 2 1 1 2 1 2 1 2 2 2 2 3 2 3 2 3 3 3 3 4 3 4 3 4 4 4 4 5 4 5 4 5 5 5 5 6 5 6 5 6 6 6 6 7 6 7 6 7 7 7 7 8 7 8 7 8 8 8 8 9 8 9 8 9 9 9 9 10 9 10 9 10 10 10 10 11 10 11 10 11 11 11 11 12 11 12 11 12 12 12 12 13 12 13 12 13 13 13 
0 1 2 1 1 2 1 2 1 2 2 1 2 3 2 2 2 2 3 2 3 3 2 3 3 3 3 3 3 4 3 4 4 3 4 4 4 4 4 4 5 4 5 5 4 5 5 5 5 5 5 6 5 6 6 5 6 6 6 6 6 6 7 6 7 7 6 7 7 7 7 7 7 8 7 8 8 7 8 8 8 8 8 8 9 8 9 9 8 9 9 9 9 9 9 10 9 10 10 9 
11 is selected
11 is selected
11 is selected
11 is selected
11 is selected
11 is selected
11 is selected
11 is selected
11 is selected
https://ideone.com/aGFitb
language:
C++ (gcc 8.3)
created:
13 days 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!