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 profit[n];
  9.     int weight[n];
  10.     for(int i = 0; i < n; i++)
  11.     {
  12.         cin>>profit[i];
  13.     }
  14.     for(int i = 0; i < n; i++)
  15.     {
  16.         cin>>weight[i];
  17.     }
  18.  
  19.     int sack[n+1][m+1];
  20.     for(int i = 0; i < n+1; i++)
  21.     {
  22.         sack[i][0] = 0;
  23.     }
  24.     for(int j = 0; j < m+1; j++)
  25.     {
  26.         sack[0][j] = 0;
  27.     }
  28.  
  29.     for(int i = 1; i < n+1; i++)
  30.     {
  31.         for(int j = 1; j < m+1; j++)
  32.         {
  33.             if(weight[i-1] > j)
  34.             {
  35.                 sack[i][j] = sack[i-1][j];
  36.             }
  37.             else
  38.             {
  39.                 sack[i][j] = max(sack[i-1][j], sack[i-1][j-weight[i-1]]+profit[i-1]);
  40.             }
  41.         }
  42.     }
  43.     for(int i = 0; i < n+1; i++)
  44.     {
  45.         for(int j = 0; j < m+1; j++)
  46.         {
  47.             cout<<sack[i][j]<<" ";
  48.         }
  49.         cout<<endl;
  50.     }
  51.  
  52.     cout<<sack[n][m]<<endl;
  53.     int i = n, j = m;
  54.  
  55.     while(i > 0)
  56.     {
  57.         if(sack[i][j] == sack[i-1][j])
  58.         {
  59.             i = i-1;
  60.             continue;
  61.         }
  62.         else
  63.         {
  64.             cout<<"Product "<<i<<" is selected"<<endl;
  65.             j = j - weight[i-1];
  66.             i = i-1;
  67.         }
  68.  
  69.     }
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  
  77.  
  78.  
  79. }
  80.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
4 8                                                                              1 2 5 6                                                                          2 3 4 5
stdout
copy 
0 0 0 0 0 0 0 0 0 
0 0 1 1 1 1 1 1 1 
0 0 1 2 2 3 3 3 3 
0 0 1 2 5 5 6 7 7 
0 0 1 2 5 6 6 7 8 
8
Product 4 is selected
Product 2 is selected
https://ideone.com/4rFaJ4
language:
C++ (gcc 8.3)
created:
10 hours 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!