fork download 
  1. #include <iostream>
  2. #define DIM 5001
  3. #define FIN "rucsac.in"
  4. #define FOUT "rucsac.out"
  5.  
  6. /*
  7.           C[i]+C[i-1][j-G[i]], G[i]<=j
  8. C[i][j] =
  9.           C[i-1][j], else
  10. */
  11.  
  12. typedef struct object {
  13.     int weight,
  14.         value;
  15. } Object;
  16.  
  17. int N, Gmax;
  18. Object arr[DIM];
  19. int C[DIM][DIM], P[DIM][DIM];
  20.  
  21. int main(int argc, char const *argv[]) {
  22.  
  23.   //freopen(FIN, "r", stdin);
  24.  
  25.   //freopen(FOUT, "w", stdout);
  26.  
  27.   std::cin>>N>>Gmax;
  28.  
  29.   for(int i = 1; i <= N; ++i) std::cin>>arr[i].weight>>arr[i].value;
  30.  
  31.   //for(int i = 1; i <= N; ++i) std::cout<<arr[i].weight<<" "<<arr[i].value<<std::endl;
  32.  
  33.   for(int i = 1; i <= N; ++i) {
  34.  
  35.     for(int j = 1; j <= Gmax; ++j) {
  36.  
  37.         if(arr[i].weight <= j && (arr[i].value + C[i-1][j-arr[i].weight]) > C[i-1][j]) {
  38.  
  39.           C[i][j] = arr[i].value + C[i-1][j-arr[i].weight];
  40.  
  41.         } else {
  42.  
  43.           C[i][j] = C[i-1][j];
  44.         }
  45.     }
  46.   }
  47.  
  48.  
  49.  
  50.   std::cout<<C[N][Gmax];
  51.   return 0;
  52. }
  53.  
Success #stdin #stdout 0.01s 7712KB
comments (?)
stdin 
6 10
3 7
3 4
1 2
1 9
2 4
1 5
stdout 
29
https://ideone.com/dTwyz6
Knapsack Discret Problem
language:
C++ (gcc 8.3)
created:
1 year 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!