fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. // Recursive function to find the maximum value
  6. int knapsackRecursive(int capacity, vector<int>& weights, vector<int>& values, int n) {
  7.     // Base case: no items left or capacity becomes 0
  8.     if (n == 0 || capacity == 0) {
  9.         return 0;
  10.     }
  11.  
  12.     // If the weight of the nth item is more than the capacity, skip this item
  13.     if (weights[n - 1] > capacity) {
  14.         return knapsackRecursive(capacity, weights, values, n - 1);
  15.     } else {
  16.         // Include the nth item or exclude it
  17.         int includeItem = values[n - 1] + knapsackRecursive(capacity - weights[n - 1], weights, values, n - 1);
  18.         int excludeItem = knapsackRecursive(capacity, weights, values, n - 1);
  19.         return max(includeItem, excludeItem);
  20.     }
  21. }
  22.  
  23. int main() {
  24.     int n; // Number of items
  25.     int capacity; // Maximum weight capacity of the knapsack
  26.  
  27.     // Example input
  28.     cout << "Enter number of items: ";
  29.     cin >> n;
  30.     cout << "Enter knapsack capacity: ";
  31.     cin >> capacity;
  32.  
  33.     vector<int> weights(n);
  34.     vector<int> values(n);
  35.  
  36.     cout << "Enter weights of items: ";
  37.     for (int i = 0; i < n; i++) {
  38.         cin >> weights[i];
  39.     }
  40.  
  41.     cout << "Enter values of items: ";
  42.     for (int i = 0; i < n; i++) {
  43.         cin >> values[i];
  44.     }
  45.  
  46.     int maxValue = knapsackRecursive(capacity, weights, values, n);
  47.     cout << "Maximum value in the knapsack: " << maxValue << endl;
  48.  
  49.     return 0;
  50. }
  51.  
Success #stdin #stdout 0s 5220KB
comments (?)
stdin
copy 
3
50
10 20 30
60 100 120
stdout
copy 
Enter number of items: Enter knapsack capacity: Enter weights of items: Enter values of items: Maximum value in the knapsack: 220
https://ideone.com/wopL2P
language:
C++14 (gcc 8.3)
created:
11 hours 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!