fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. //#define mx 1000
  4. //int price[mx],weight[mx],dp[mx][mx];
  5.  
  6. int max_n = 500, max_W = 2000000;
  7.  
  8. int knapSack(int wt[], int val[], int n, int W)
  9. {
  10.     int *dpPrev, *dpCurr, *tmp;
  11.     dpPrev = new int[max_W+1];
  12.     dpCurr = new int[max_W+1];
  13.  
  14.     int c = 0;
  15.  
  16.     for(int i=0; i<=max_n; i++)
  17.     {
  18.         for(int m=0; m<=max_W; m++)
  19.         {
  20.         	c++;
  21.             if (i==0 || m==0)        dpCurr[m] = 0;
  22.  
  23.             else if (wt[i-1] <= m)   dpCurr[m] = max(val[i-1] + dpPrev[m-wt[i-1]],  dpPrev[m]);
  24.  
  25.             else                     dpCurr[m] = dpPrev[m];
  26.         }
  27.  
  28.         tmp = dpPrev;
  29.         dpPrev = dpCurr;
  30.         dpCurr = tmp;
  31.     }
  32.  
  33.     cout<<c<<endl;
  34.     return dpPrev[W];
  35. }
  36.  
  37.  
  38. int main()
  39. {
  40.     int n,W,*va,*wt;
  41.  
  42.     cin>>W>>n;
  43.  
  44.     va = new int[max_n];
  45.  
  46.     wt = new int[max_n];
  47.  
  48.     for(int i=0;i<n;i++)   cin>>va[i]>>wt[i];
  49.  
  50.     for(int i=n;i<max_n;i++){
  51.         va[i] = i;
  52.         wt[i] = 2*i;
  53.     }
  54.  
  55.     cout<<knapSack(wt, va, n, W)<<endl;
  56.  
  57.     return 0;
  58. }
Success #stdin #stdout 1.5s 19104KB
comments (?)
stdin
copy 
10 3
7 3
8 8
4 6
stdout
copy 
1002000501
11
https://ideone.com/KXwmCL
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!