fork download
copy 
  1. #include <cstdio>
  2. #include <cassert>
  3. #include <algorithm>
  4.  
  5. const int MAX_NUM_OBJECTS = 30;
  6. const int MAX_NUM_WEIGHTS = 100;
  7. int knapsack[MAX_NUM_OBJECTS+5][MAX_NUM_WEIGHTS+5];
  8. bool knapsack_taken[MAX_NUM_OBJECTS+5][MAX_NUM_WEIGHTS+5];
  9. int knapsack_n_taken[MAX_NUM_OBJECTS+5][MAX_NUM_WEIGHTS+5];
  10.  
  11. struct Object { 
  12.     int _weight, _value; 
  13.     int weight() const { return _weight; } 
  14.     int value() const { return _value; } 
  15. } objects[MAX_NUM_OBJECTS];
  16.  
  17. void print_object(int nObject, int nWeight) {
  18.     if (nObject != 0 and nWeight != 0) {
  19.         if (knapsack_n_taken[nObject][nWeight]) {
  20.             int cur_object_value = objects[nObject].value();
  21.             int cur_object_weight = objects[nObject].weight();
  22.             print_object(nObject-1, nWeight-cur_object_weight);
  23.             printf("  %d %d\n", cur_object_weight, cur_object_value);
  24.         } else {
  25.             print_object(nObject-1, nWeight);
  26.         }
  27.     }
  28. }
  29.  
  30. int main() {
  31.     int max_weight, nObject, posCase = 1;
  32.     while (scanf("%d%d", &max_weight, &nObject) == 2) {
  33.         assert(max_weight <= MAX_NUM_WEIGHTS);
  34.         assert(nObject < MAX_NUM_OBJECTS);
  35.         for (int i = 1; i <= nObject; ++i) {
  36.             scanf("%d%d", &objects[i]._weight, &objects[i]._value);
  37.             assert(objects[i].weight() <= MAX_NUM_WEIGHTS);
  38.         }
  39.  
  40.         for (int i = 0; i <= max_weight; ++i) knapsack[0][i] = knapsack_n_taken[0][i] = 0;
  41.         for (int i = 0; i <= nObject; ++i) knapsack[i][0] = knapsack_n_taken[i][0] = 0;
  42.  
  43.         for (int i = 1; i <= nObject; ++i)
  44.             for (int k = 1; k <= max_weight; ++k) {
  45.                 int cur_object_weight = objects[i].weight();
  46.                 int cur_object_value = objects[i].value();
  47.  
  48.                 int prev_value = knapsack[i-1][k];
  49.                 int reduced_weight = k-cur_object_weight;
  50.                 int taken_value = cur_object_value + knapsack[i-1][reduced_weight];
  51.  
  52.                 knapsack[i][k] = prev_value;
  53.                 knapsack_taken[i][k] = false;
  54.                 knapsack_n_taken[i][k] = knapsack_n_taken[i-1][k];
  55.  
  56.                 if (k >= cur_object_weight and taken_value > prev_value) {
  57.                     knapsack[i][k] = taken_value;
  58.                     knapsack_taken[i][k] = true;
  59.                     knapsack_n_taken[i][k] = knapsack_n_taken[i-1][reduced_weight] + 1; 
  60.                 }
  61.             }
  62.  
  63.  
  64.         printf("Case #%d\n", posCase++);
  65.         printf("  max value : %d\n", knapsack[nObject][max_weight]);
  66.         printf("  num of object : %d\n", knapsack_n_taken[nObject][max_weight]);
  67.         print_object(nObject, max_weight);
  68.     }
  69.     return 0;
  70. }
Success #stdin #stdout 0s 3496KB
comments (?)
stdin
copy 
50
3
10 60
20 100
30 120
stdout
copy 
Case #1
  max value : 220
  num of object : 2
  20 100
  30 120
https://ideone.com/5XZhWQ
language:
C++14 (gcc 8.3)
created:
9 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!