fork(7) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. void printKnapsack(const vector<int>& knapsack) {
  6.     cout << "[";
  7.     for (int x : knapsack)      // range for : x will be called for each int in the knapsack vector
  8.         cout << x <<" ";
  9.     cout<<"]"<<endl; 
  10. }
  11.  
  12. void print_solutions(int current_item, vector<int>& knapsack, int current_sum, const vector<int>& items, int limit) {
  13.     //if all items have been processed print the solution and return
  14.     if (current_item == items.size() ) {
  15.         printKnapsack(knapsack);
  16.         return;
  17.     };
  18.  
  19.     //don't take the current item and go check others
  20.     vector<int> knapcopy = knapsack; 
  21.     print_solutions(current_item + 1, knapcopy, current_sum, items, limit);
  22.  
  23.     //take the current item if the value doesn't exceed the limit
  24.     if (current_sum + items[current_item] <= limit) {
  25.         knapsack.push_back(items[current_item]);
  26.         current_sum += items[current_item];
  27.         //current item taken go check others
  28.         print_solutions(current_item + 1, knapsack, current_sum, items, limit);
  29.     };
  30. };
  31.  
  32.  
  33. int main() {
  34.     int current_item = 0;
  35.     int current_sum = 0;
  36.     int limit, n;
  37.     cout << "Type the maximum weight ";
  38.     cin >> limit;
  39.     cout << "How many items?  ";
  40.     cin >> n;
  41.  
  42.     vector<int> knapsack;   // empty vector
  43.     vector<int> items(n);   // vector with n elements
  44.  
  45.     cout << "Type weights.";
  46.     for (int i = 0; i < n; i++) {
  47.         cin >> items[i];
  48.     };
  49.  
  50.     print_solutions(0, knapsack, 0, items, limit);  // n not needed
  51.  
  52.     return 0;
  53.  
  54. }
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
7
5
1 1 3 4 5
stdout
copy 
Type the maximum weight How many items?  Type weights.[]
[5 ]
[4 ]
[3 ]
[3 4 ]
[1 ]
[1 5 ]
[1 4 ]
[1 3 ]
[1 ]
[1 5 ]
[1 4 ]
[1 3 ]
[1 1 ]
[1 1 5 ]
[1 1 4 ]
[1 1 3 ]
https://ideone.com/CwUANx
language:
C++14 (gcc 8.3)
created:
8 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!