Table of contents

0-1 Knapsack Problem

Given n items, each with a weight and value, and a knapsack of a fixed capacity W, find the maximum value that can be obtained by selecting items such that their total weight does not exceed the knapsack's capacity. Each item can either be included or excluded (0-1), meaning you cannot take a fraction of an item.

Input/Output Examples

plaintext
Example 1:
Input:
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
Output: 9
Explanation: You can select items with weights 3 and 4 for a total value of 9.

Example 2:
Input:
weights = [2, 3, 4]
values = [3, 4, 5]
capacity = 5
Output: 7
Explanation: You can select items with weights 2 and 3 for a total value of 7.

Approach to implement 0-1 knapsack Problem

  1. Dynamic Programming Approach:
    • Use a 2D DP table dp[i][w] where i represents the first i items and w represents the weight limit.
    • dp[i][w] stores the maximum value that can be obtained with the first i items and a knapsack capacity of w.
    • For each item i, there are two options:
      • Exclude the item: The value is dp[i-1][w].
      • Include the item (if the weight allows it): The value is dp[i-1][w - weight[i-1]] + value[i-1].
    • The recurrence relation is:
      dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1]) if weight[i-1] <= w.
  2. Algorithm:
    • Initialize a DP table with dimensions (n+1) x (capacity+1) filled with 0.
    • Traverse through each item and update the DP table.
    • The final answer will be in dp[n][capacity].
  3. Edge Cases:
    • If there are no items or the capacity is 0, the result is 0.
    • If an item's weight is greater than the current capacity, it can't be included.

C++ Program to implement 0-1 Knapsack Problem

cpp
#include <iostream>
#include <vector>
using namespace std;

// Function to solve the 0-1 Knapsack problem using dynamic programming
int knapsack(int capacity, vector<int>& weights, vector<int>& values, int n) {
    // Initialize a DP table with dimensions (n+1) x (capacity+1)
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    // Build the DP table
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w]; // Exclude the item
            }
        }
    }

    // The final answer is in dp[n][capacity]
    return dp[n][capacity];
}

int main() {
    vector<int> weights = {1, 3, 4, 5};
    vector<int> values = {1, 4, 5, 7};
    int capacity = 7;
    int n = weights.size();

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

    return 0;
}

Java Program to implement 0-1 Knapsack Problem

java
public class Knapsack {

    // Function to solve the 0-1 Knapsack problem using dynamic programming
    public static int knapsack(int capacity, int[] weights, int[] values, int n) {
        // Initialize a DP table with dimensions (n+1) x (capacity+1)
        int[][] dp = new int[n + 1][capacity + 1];

        // Build the DP table
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][w] = dp[i - 1][w]; // Exclude the item
                }
            }
        }

        // The final answer is in dp[n][capacity]
        return dp[n][capacity];
    }

    public static void main(String[] args) {
        int[] weights = {1, 3, 4, 5};
        int[] values = {1, 4, 5, 7};
        int capacity = 7;
        int n = weights.length;

        int result = knapsack(capacity, weights, values, n);
        System.out.println("Maximum value: " + result);
    }
}

Python Program to implement 0-1 Knapsack Problem

python
# Function to solve the 0-1 Knapsack problem using dynamic programming
def knapsack(capacity, weights, values, n):
    # Initialize a DP table with dimensions (n+1) x (capacity+1)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    # Build the DP table
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w] # Exclude the item

    # The final answer is in dp[n][capacity]
    return dp[n][capacity]

# Example usage
if __name__ == "__main__":
    weights = [1, 3, 4, 5]
    values = [1, 4, 5, 7]
    capacity = 7
    n = len(weights)

    result = knapsack(capacity, weights, values, n)
    print(f"Maximum value: {result}")

Time Complexity:

  • O(n * W): The time complexity is proportional to the number of items n and the knapsack capacity W, since we fill a DP table of size (n+1) x (W+1).

Space Complexity:

  • O(n * W): The space complexity is also proportional to the size of the DP table, which is (n+1) x (W+1).

DSA

Related Articles