allia

рюкзак 3

Dec 3rd, 2020 (edited)
544
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2.  
  3. using namespace std;
  4.  
  5.  void Print(int s, int n, int **result, int *w)
  6. {
  7.   if (result[s][n]==0)
  8.     return;        
  9.                  
  10.   else if (result[s-1][n] == result[s][n])
  11.     Print(s-1, n, result, w);  
  12.   else
  13.   {                              
  14.     Print(s-1, n-w[s-1], result, w);
  15.     cout << s << " ";    
  16.   }
  17. }
  18.  
  19. int main()
  20. {
  21.  int N, W;
  22.  cin >> N >> W;
  23.  
  24.  int *arr = new int[N];
  25.  for (int i = 0; i < N; i++)
  26.    cin >> arr[i];
  27.  
  28.  int *w = new int[N];
  29.  for (int i = 0; i < N; i++)
  30.    cin >> w[i];
  31.  
  32. int **result = new int*[N+1];
  33.  
  34. for (int i = 0; i <= N; i++)
  35.    result[i] = new int[W+1];
  36.  
  37. for (int j=0; j <= W; j++)
  38.    result[0][j] = 0;
  39.  
  40. for(int s=1 ;s <= N; ++s)      
  41.     for (int n=0; n <= W; ++n)  
  42.     {
  43.         if ( n >= w[s-1] && ( result[s-1][n-w[s-1]]+arr[s-1] > result[s-1][n]))
  44.             result[s][n] = result[s-1][n-w[s-1]]+arr[s-1];
  45.         else result[s][n] = result[s-1][n];
  46.     }
  47.  
  48.  for (int i=0; i<= N; i++)
  49.     {
  50.       for (int j=0; j<= W; j++)
  51.       {
  52.         cout.width(3);
  53.         cout << result[i][j] << " ";
  54.       }
  55.      cout << endl;
  56.     }
  57.  
  58. Print(N, W, result, w);
  59.  
  60. }
RAW Paste Data