fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     int n, m;
  6.     cin>>n>>m;
  7.     int profit[n];
  8.     int weight[n];
  9.     for(int i = 0; i < n; i++)
  10.     {
  11.         cin>>profit[i];
  12.     }
  13.     for(int i = 0; i < n; i++)
  14.     {
  15.         cin>>weight[i];
  16.     }
  17.  
  18.     int sack[n+1][m+1];
  19.     for(int i = 0; i < n+1; i++)
  20.     {
  21.         sack[i][0] = 0;
  22.     }
  23.     for(int j = 0; j < m+1; j++)
  24.     {
  25.         sack[0][j] = 0;
  26.     }
  27.  
  28.     for(int i = 1; i < n+1; i++)
  29.     {
  30.         for(int j = 1; j < m+1; j++)
  31.         {
  32.             if(weight[i-1] > j)
  33.             {
  34.                 sack[i][j] = sack[i-1][j];
  35.             }
  36.             else
  37.             {
  38.                 sack[i][j] = max(sack[i-1][j], sack[i-1][j-weight[i-1]] + profit[i-1]);
  39.             }
  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.  
  54.     int i = n, j = m;
  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<<"Object "<<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.  
Success #stdin #stdout 0s 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
Object 4 is selected
Object 2 is selected
https://ideone.com/ThaCOf
language:
C++ (gcc 8.3)
created:
3 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!