0-1 Knapsack Problem

0/1 Knapsack Problem

The 0/1 Knapsack Problem is a classic problem in dynamic programming and combinatorial optimization. In this problem, we are given a set of items, each with a weight and a value, and we need to determine the maximum value we can achieve by selecting some of these items to put in a knapsack, without exceeding its weight capacity.

Problem Statement:

• We are given n items, where each item i has:
  • A value v[i]
  • A weight w[i]
• We have a knapsack with a weight capacity W.
• The goal is to find the maximum value that can be achieved by putting some subset of these items in the knapsack, such that the total weight does not exceed W.

Mathematical Formulation:

Let’s define a state dp[i][w] as the maximum value achievable with the first i items and a knapsack weight capacity w.

The recurrence relation for the 0/1 knapsack problem can be written as:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - w[i]] + v[i])

Where:

• dp[i-1][w]: This represents the case where we do not include item i.
• dp[i-1][w - w[i]] + v[i]: This represents the case where we include item i, so the new weight is reduced by the weight of the item, and the value increases by the value of that item.

The base cases are:

• dp[0][w] = 0 for all w (If there are no items, the maximum value is 0 for any capacity).
• dp[i][0] = 0 for all i (If the knapsack capacity is 0, the maximum value is 0 for any number of items).

Approach:

We can solve the 0/1 Knapsack Problem using dynamic programming by filling a 2D table, where each entry represents the maximum value obtainable for a given number of items and knapsack capacity.

Solution:

1. Top-Down Approach (Memoization)

In this approach, we use recursion combined with memoization to store previously computed results.

#include <iostream>
#include <vector>

std::vector<std::vector<int>> memo;

int knapsack(int W, const std::vector<int>& weights, const std::vector<int>& values, int n) {
    // Base case: If no items or capacity is 0, return 0
    if (n == 0 || W == 0)
        return 0;

    // If the result is already computed, return the memoized value
    if (memo[n][W] != -1)
        return memo[n][W];

    // If the weight of the current item is greater than the capacity, we can't include it
    if (weights[n - 1] > W)
        return memo[n][W] = knapsack(W, weights, values, n - 1);
    
    // Return the maximum of including or excluding the current item
    return memo[n][W] = std::max(
        knapsack(W, weights, values, n - 1),  // Exclude item n
        values[n - 1] + knapsack(W - weights[n - 1], weights, values, n - 1)  // Include item n
    );
}

int main() {
    int W = 50;  // Knapsack capacity
    std::vector<int> weights = {10, 20, 30};  // Weights of items
    std::vector<int> values = {60, 100, 120}; // Values of items
    int n = weights.size();  // Number of items

    // Initialize memoization table with -1 (indicating not computed yet)
    memo.resize(n + 1, std::vector<int>(W + 1, -1));

    std::cout << "Maximum value in knapsack = " << knapsack(W, weights, values, n) << std::endl;

    return 0;
}

Explanation:

• The function knapsack(W, weights, values, n) calculates the maximum value that can be achieved with the first n items and a knapsack capacity W.
• If the weight of the current item exceeds the current capacity W, we cannot include the item and solve the subproblem for the remaining items.
• The results are memoized in a 2D table memo to avoid recomputation.

Time Complexity:

• Time Complexity: O(n * W), where n is the number of items and W is the knapsack capacity. This is because we are filling a table of size (n+1) x (W+1).
• Space Complexity: O(n * W) due to the memoization table.

2. Bottom-Up Approach (Tabulation)

In this approach, we build the solution iteratively, starting from the base case and solving for all subproblems.

#include <iostream>
#include <vector>

int knapsack(int W, const std::vector<int>& weights, const std::vector<int>& values, int n) {
    // DP table to store maximum value for each subproblem
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));

    // Fill the DP table
    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (weights[i - 1] <= w) {
                // Maximize value between including or excluding the item
                dp[i][w] = std::max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                // If weight of item is more than the current capacity, exclude it
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // The last cell contains the maximum value
    return dp[n][W];
}

int main() {
    int W = 50;  // Knapsack capacity
    std::vector<int> weights = {10, 20, 30};  // Weights of items
    std::vector<int> values = {60, 100, 120}; // Values of items
    int n = weights.size();  // Number of items

    std::cout << "Maximum value in knapsack = " << knapsack(W, weights, values, n) << std::endl;

    return 0;
}

Explanation:

• We create a 2D DP table dp where dp[i][w] represents the maximum value achievable with the first i items and a knapsack capacity w.
• We iterate over all items and capacities, filling the table using the recurrence relation:
  • If the current item's weight is less than or equal to the current capacity, we calculate the maximum of including or excluding the item.
  • If the current item's weight is greater than the current capacity, we exclude the item.

Time Complexity:

• Time Complexity: O(n * W), where n is the number of items and W is the knapsack capacity. We are iterating over all items and all capacities.
• Space Complexity: O(n * W) due to the DP table.

Space Optimization (Space Complexity Reduction)

The DP solution can be optimized to use O(W) space by using only two 1D arrays instead of a 2D array. The idea is that at any point, the current state only depends on the previous row (previous iteration), so we don't need to keep the entire DP table.

Here’s the optimized code:

#include <iostream>
#include <vector>

int knapsack(int W, const std::vector<int>& weights, const std::vector<int>& values, int n) {
    std::vector<int> dp(W + 1, 0); // 1D DP table
    
    for (int i = 1; i <= n; ++i) {
        for (int w = W; w >= weights[i - 1]; --w) {  // Traverse in reverse to prevent overwriting previous values
            dp[w] = std::max(dp[w], dp[w - weights[i - 1]] + values[i - 1]);
        }
    }

    return dp[W];
}

int main() {
    int W = 50;  // Knapsack capacity
    std::vector<int> weights = {10, 20, 30};  // Weights of items
    std::vector<int> values = {60, 100, 120}; // Values of items
    int n = weights.size();  // Number of items

    std::cout << "Maximum value in knapsack = " << knapsack(W, weights, values, n) << std::endl;

    return 0;
}

Time Complexity: O(n * W)

Space Complexity: O(W), because we only use a single array of size W+1.

Conclusion

The 0/1 Knapsack Problem is a typical example of a