fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 20000004
  4. int mat[2][MAX],val[MAX],wt[MAX];
  5.  
  6. int KnapSack(int val[], int wt[], int n, int W)
  7. {
  8.     // matrix to store final result
  9.     // iterate through all items
  10.     int i = 0;
  11.     while (i < n) // one by one traverse each element
  12.     {
  13.         int j = 0; // traverse all wieghts j <= W
  14.  
  15.         // if i is odd that mean till now we have odd
  16.         // number of elements so we store result in 1th
  17.         // indexed row
  18.         if (i&1)
  19.         {
  20.             while (++j <= W) // check for each value
  21.             {
  22.                 if (wt[i] <= j) // include element
  23.                     mat[1][j] = max(val[i] + mat[0][j-wt[i]],
  24.                                     mat[0][j] );
  25.                 else           // exclude element
  26.                     mat[1][j] = mat[0][j];
  27.             }
  28.  
  29.         }
  30.  
  31.         // if i is even that mean till now we have even number
  32.         // of elements so we store result in 0th indexed row
  33.         else
  34.         {
  35.             while(++j <= W)
  36.             {
  37.                 if (wt[i] <= j)
  38.                     mat[0][j] = max(val[i] + mat[1][j-wt[i]],
  39.                                      mat[1][j]);
  40.                 else
  41.                     mat[0][j] = mat[1][j];
  42.             }
  43.         }
  44.         i++;
  45.     }
  46.  
  47.     // Return mat[0][W] if n is odd, else mat[1][W]
  48.     return (n&1)? mat[0][W] : mat[1][W];
  49. }
  50.  
  51. int main()
  52. {
  53. ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  54.  
  55. int W,n,i;
  56.   cin>>W>>n;
  57.   for(i=0;i<n;++i)
  58.     cin>>val[i]>>wt[i];
  59.  
  60.     cout << KnapSack(val, wt, n, W) ;
  61.     return 0;
  62. }
  63.  
Success #stdin #stdout 0s 315392KB
comments (?)
stdin
copy 
10 3
7 3
8 8
4 6
stdout
copy 
11
https://ideone.com/4ybge2
language:
C++ 4.3.2 (gcc-4.3.2)
created:
7 years 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!