0/1 Knapsack Problem Code In C++

Suzhoumeite

5 min read

·

Jul 17, 2024

32

Share

0/1 Knapsack Problem Code in C++

The 0/1 knapsack problem is a classic problem in computer science and operations research that involves finding the optimal way to pack a set of items of different weights and values into a knapsack of limited capacity. The goal is to maximize the total value of the items in the knapsack without exceeding its capacity.

Problem Statement

Given a set of n items, each with a weight w_i and a value v_i, and a knapsack of capacity W, determine the subset of items to include in the knapsack to maximize the total value while not exceeding the knapsack capacity.

0/1 Knapsack Problem Code in C++

Here is a C++ implementation of the 0/1 knapsack problem using dynamic programming:

#include 
#include 

using namespace std;

int knapsack(int W, int n, vector wt, vector val) {
  vector> dp(W + 1, vector(n + 1, 0));

  for (int i = 1; i <= W; i++) {
    for (int j = 1; j <= n; j++) {
      if (wt[j - 1] <= i) {
        dp[i][j] = max(val[j - 1] + dp[i - wt[j - 1]][j - 1], dp[i][j - 1]);
      } else {
        dp[i][j] = dp[i][j - 1];
      }
    }
  }

  return dp[W][n];
}

int main() {
  int W = 50; // knapsack capacity
  int n = 5; // number of items
  vector wt = {10, 20, 30, 40, 50}; // weights
  vector val = {10, 30, 40, 50, 60}; // values

  int max_val = knapsack(W, n, wt, val);
  cout << "Maximum value in knapsack: " << max_val << endl;

  return 0;
}

Explanation

The code uses a 2D array dp to store the maximum value that can be obtained with i capacity and considering the first j items. The recurrence relation is:

• If the weight of the j-th item is less than or equal to the current capacity i, then the maximum value is the maximum of two options:
  • Including the j-th item and recursively solving for the remaining capacity i - wt[j - 1] and considering the first j - 1 items.
  • Excluding the j-th item and recursively solving for the current capacity i and considering the first j - 1 items.
• If the weight of the j-th item is greater than the current capacity i, then the maximum value is the same as excluding the j-th item and recursively solving for the current capacity i and considering the first j - 1 items.

The final answer is stored in dp[W][n].

Time Complexity

The time complexity of the above implementation is O(W * n), where W is the knapsack capacity and n is the number of items.

Space Complexity

The space complexity of the above implementation is O(W * n), which is used to store the 2D array dp.

I hope this helps! Let me know if you have any questions.