0/1 Knapsack Problem Using Dynamic Programming Code In C++

Suzhoumeite

6 min read

·

Jul 17, 2024

58

Share

0/1 Knapsack Problem using Dynamic Programming in C++

Introduction

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 problem is called "0/1" because each item can either be included (1) or excluded (0) from the knapsack.

Problem Statement

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

Dynamic Programming Solution

Dynamic programming is a powerful technique for solving optimization problems by breaking them down into smaller subproblems and solving each subproblem only once. The 0/1 knapsack problem can be solved using dynamic programming by constructing a 2D table dp where dp[i][w] represents the maximum value that can be obtained with i items and a knapsack capacity of w.

C++ Code

Here is the C++ code for solving the 0/1 knapsack problem using dynamic programming:

#include 
#include 

using namespace std;

int knapsack(vector weights, vector values, int capacity) {
  int n = weights.size();
  vector> dp(n + 1, vector(capacity + 1, 0));

  for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= capacity; w++) {
      if (weights[i - 1] <= w) {
        dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }

  return dp[n][capacity];
}

int main() {
  vector weights = {2, 3, 5, 7};
  vector values = {10, 20, 30, 40};
  int capacity = 10;

  int maxValue = knapsack(weights, values, capacity);
  cout << "Maximum value: " << maxValue << endl;

  return 0;
}

Explanation

The knapsack function takes as input three parameters:

• weights: a vector of item weights
• values: a vector of item values
• capacity: the knapsack capacity

The function returns the maximum value that can be obtained with the given items and knapsack capacity.

The dynamic programming table dp is constructed using two nested loops. The outer loop iterates over the items, and the inner loop iterates over the knapsack capacities from 1 to capacity. For each cell dp[i][w], the function checks if the i-th item can be included in the knapsack with capacity w. If it can, the function calculates the maximum value by considering two options:

• Include the i-th item and recursively call the knapsack function with the remaining capacity w - weights[i - 1].
• Exclude the i-th item and use the maximum value from the previous row dp[i - 1][w].

The function returns the maximum value in the bottom-right cell of the dp table, which represents the maximum value that can be obtained with all items and the given knapsack capacity.

Time Complexity

The time complexity of the dynamic programming solution is O(nW), where n is the number of items and W is the knapsack capacity.

Space Complexity

The space complexity of the dynamic programming solution is O(nW), since we need to store the dp table with n rows and W columns.

I hope this helps! Let me know if you have any questions or need further clarification.