ulvis.paste.net

Paste Search Dynamic
Recent pastes
knapSack
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int ans;
  6.  
  7. int max(int a, int b)
  8. {
  9.     return (a > b) ? a : b;
  10. }
  11.  
  12. int knapSack(int W, int wt[], int val[], int n)
  13. {
  14.     int i, w;
  15.     int K[n + 1][W + 1];
  16.      for (i = 0; i <= n; i++)
  17.     {
  18.         for (w = 0; w <= W; w++)
  19.         {
  20.             if (i == 0 || w == 0){
  21.                 K[i][w] = 0;
  22.  
  23.  
  24.             }
  25.             else if (wt[i - 1] <= w)
  26.                { K[i][w]
  27.                         = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
  28.  
  29.  
  30.                }  else{
  31.                 K[i][w] = K[i - 1][w];
  32.                 ans++;
  33.                         }
  34.         }
  35.     }
  36.  
  37.     return K[n][W];
  38. }
  39.  
  40. int main()
  41. {
  42.     int n, W;
  43.     cin >> n;
  44.     cin >> W;
  45.     int val[n], wt[n];
  46.     for (int i = 0; i < n; i++)
  47.     {
  48.         cin >> val[i];
  49.         cin >> wt[i];
  50.     }
  51.  
  52.  
  53.     cout << knapSack(W, wt, val, n)<<endl;
  54.     cout <<ans <<endl;
  55.     return 0;
  56. }
Parsed in 0.007 seconds