рюкзак 3

#include<iostream>

using namespace std;

 void Print(int s, int n, int **result, int *w)
{
  if (result[s][n]==0)
    return;

  else if (result[s-1][n] == result[s][n])
    Print(s-1, n, result, w);
  else
  {
    Print(s-1, n-w[s-1], result, w);
    cout << s << " ";
  }
}

int main()
{
 int N, W;
 cin >> N >> W;

 int *arr = new int[N];
 for (int i = 0; i < N; i++)
   cin >> arr[i];

 int *w = new int[N];
 for (int i = 0; i < N; i++)
   cin >> w[i];

int **result = new int*[N+1];

for (int i = 0; i <= N; i++)
   result[i] = new int[W+1];

for (int j=0; j <= W; j++)
   result[0][j] = 0;

for(int s=1 ;s <= N; ++s)
    for (int n=0; n <= W; ++n)
    {
        if ( n >= w[s-1] && ( result[s-1][n-w[s-1]]+arr[s-1] > result[s-1][n]))
            result[s][n] = result[s-1][n-w[s-1]]+arr[s-1];
        else result[s][n] = result[s-1][n];
    }

 for (int i=0; i<= N; i++)
    {
      for (int j=0; j<= W; j++)
      {
        cout.width(3);
        cout << result[i][j] << " ";
      }
     cout << endl;
    }

Print(N, W, result, w);

}