0-1 Knapsack Problem

Problem

Given n items with their respective weights (w1, w2, ..., wn) and values (v1, v2, ..., vn), along with a total capacity weight W of the knapsack, the goal is to maximise the total value of items placed in the knapsack. Each item can be used at most once, and the total weight of selected items must not exceed the knapsack’s capacity.

Examples

Example 1

1
2
3
4
5
6
7


Input:  
Weights = [2, 3, 4], Values = [4, 5, 6], Capacity = 5  
Output:  
Maximum value = 9  
Explanation:  
- We include item1 (weight=2, value=4) and item2 (weight=3, value=5),  
achieving a total weight=5 and total value=9.  

Example 2

1
2
3
4
5
6
7


Input:  
Weights = [1, 2, 3], Values = [6, 10, 12], Capacity = 5  
Output:  
Maximum value = 22  
Explanation:  
- We include item2 (weight=2, value=10) and item3 (weight=3, value=12),  
achieving a total weight=5 and total value=22.  

Variation

Unlike Fractional Knapsack, where item divisibility is the key, Discrete Knapsack focuses on optimising value using whole items.

Discrete knapsack problems come in two types:

With repetitions: Items can be selected multiple times: Unbounded Knapsack Problem
Without repetitions: Each item can only be selected once, which is the current problem: 0-1 Knapsack Problem

Additionally, there are special cases of the knapsack problem:

All items have equal weight: In this scenario, the goal is to maximise profit as all items weigh the same. Sorting items by value and then picking the highest-value items will solve this variant using a greedy approach.
All items have equal value: If all items have the same value, selecting as many items as possible within the weight limit becomes the target. Sorting items by size and selecting the smallest ones until the knapsack is full provides an efficient solution.

Another prominent instance of the knapsack problem is the Subset Sum Problem, where each item’s value is proportional to its size. For example, consider a collection of gold weights: heavier weights hold more value, and the goal is to fill the knapsack while minimising leftover space. Additionally, this problem appears in cases where you aim to achieve a specific total (C) as closely as possible.

However, this subset sum problem cannot be solved using a greedy algorithm because it is NP-complete. This means it belongs to a class of problems for which no known polynomial-time solutions exist unless P = NP is proven. It is often linked to the Subset Sum Problem and related algorithms like the Integer Partition Algorithm.

Solution

Method 1 - Recursion

Whenever an algorithmic problem like this arises, identifying patterns in the statement can help connect it to known approaches:

Choices: For each item, there are two possibilities:
- Include the item (if the weight allows).
- Exclude the item.
Optimisation Problem: The goal is to maximise the total value within given constraints.

The problem lends itself naturally to a recursive solution, where we break it into smaller subproblems (optimising value for smaller capacities and fewer items). Dynamic programming is an optimised recursion, storing results of computed subproblems to avoid redundant calculations.

Recursive Structure

Let Knapsack(W, n) represent the maximum value obtainable for a knapsack of capacity W using the first n items. For every item, we follow these steps:

Weight exceeds capacity: If the item’s weight is greater than the knapsack capacity (wt[n] > W), the item cannot be included. We move to the next item:
1

Knapsack(W, n) = Knapsack(W, n-1)
Weight fits in the knapsack: If the item’s weight allows it to fit (wt[n] <= W), we have two options:
- Include the item: Add its value (val[n]) and solve the reduced problem for the remaining capacity (W - wt[n]).
- Exclude the item: Solve the problem without it. The result is the maximum of these two choices:
1

Knapsack(W, n) = max(Knapsack(W, n-1), Knapsack(W - wt[n], n-1) + val[n])
Base condition: The smallest valid input occurs when either no items are left (n = 0) or the knapsack has zero capacity (W = 0):
1 2

Knapsack(W, 0) = 0 Knapsack(0, n) = 0

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


#include <iostream>
#include <algorithm>
using namespace std;

class Solution {
public:
    int knapsack(int capacity, int weights[], int values[], int n) {
        // Base Case: No items left or capacity exhausted
        if (n == 0 || capacity == 0)
            return 0;

        // If the current item exceeds the capacity, exclude it
        if (weights[n - 1] > capacity)
            return knapsack(capacity, weights, values, n - 1);

        // Otherwise, choose the maximum of including or excluding the current item
        else {
            int includeItem = values[n - 1] + knapsack(capacity - weights[n - 1], weights, values, n - 1);
            int excludeItem = knapsack(capacity, weights, values, n - 1);
            return max(includeItem, excludeItem);
        }
    }
};

// Example usage
int main() {
    Solution solution;
    int weights[] = {2, 3, 4};
    int values[] = {4, 5, 6};
    int capacity = 5;
    int n = sizeof(weights) / sizeof(weights[0]);
    cout << "Maximum value: " << solution.knapsack(capacity, weights, values, n) << endl;
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
    public int knapsack(int W, int[] weights, int[] values, int n) {
        // Base Case: No items left or capacity exhausted
        if (n == 0 || W == 0)
            return 0;

        // If the current item exceeds the capacity, exclude it
        if (weights[n - 1] > W)
            return knapsack(W, weights, values, n - 1);

        // Otherwise, choose the maximum of including or excluding the current item
        else {
            int includeItem = values[n - 1] + knapsack(W - weights[n - 1], weights, values, n - 1);
            int excludeItem = knapsack(W, weights, values, n - 1);
            return Math.max(includeItem, excludeItem);
        }
    }

    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] weights = {2, 3, 4};
        int[] values = {4, 5, 6};
        int capacity = 5;
        System.out.println("Maximum value: " + solution.knapsack(capacity, weights, values, weights.length));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def knapsack(self, W, weights, values, n):
        # Base Case: No items left or capacity exhausted
        if n == 0 or W == 0:
            return 0

        # If the current item exceeds the capacity, exclude it
        if weights[n - 1] > W:
            return self.knapsack(W, weights, values, n - 1)

        # Otherwise, choose the maximum of including or excluding the current item
        else:
            include_item = values[n - 1] + self.knapsack(W - weights[n - 1], weights, values, n - 1)
            exclude_item = self.knapsack(W, weights, values, n - 1)
            return max(include_item, exclude_item)


# Example usage:
solution = Solution()
weights = [2, 3, 4]
values = [4, 5, 6]
capacity = 5
print("Maximum value:", solution.knapsack(capacity, weights, values, len(weights)))

Complexity

⏰ Time complexity: O(2^n) where n is number of items. In the worst case, the recursion explores all subproblems, where each can be included or excluded, leading to O(2^n)
🧺 Space complexity: O(n) as recursion depth is proportional to number of items.

Method 2 - Top-down DP using memoized solution

Memoization improves the recursive approach by storing the results of previously solved subproblems in a table. This avoids redundant computations and transforms the exponential complexity of recursion into a more efficient polynomial complexity.

Intuition

In the recursive solution, we recompute results for the same inputs multiple times due to overlapping subproblems. The memoized solution addresses this issue by storing computed values in a 2D table, memo[n][W], where:

n represents the number of items being considered.
W represents the current capacity of the knapsack.

If a value for memo[n][W] is computed, it is reused instead of recalculating the result.

Recursive Relation Revisited

The recursive relation remains the same:

Weight exceeds capacity: If the item’s weight (wt[n]) exceeds the current capacity W, exclude it:
1

memo[n][W] = memo[n-1][W]
Weight fits: If the item can fit, compute the maximum value of including or excluding the item:
1

memo[n][W] = max(memo[n-1][W], memo[n-1][W-wt[n]] + val[n])

Base Conditions

memo[0][W] = 0 → No items, value is 0.
memo[n][0] = 0 → No capacity, value is 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


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

class Solution {
public:
    int knapsackMemo(int capacity, int weights[], int values[], int n, vector<vector<int>>& memo) {
        // Base Case: No items left or capacity exhausted
        if (n == 0 || capacity == 0)
            return 0;

        // If the result for this subproblem is already computed
        if (memo[n][capacity] != -1)
            return memo[n][capacity];

        // If the current item's weight exceeds the remaining capacity
        if (weights[n - 1] > capacity) {
            memo[n][capacity] = knapsackMemo(capacity, weights, values, n - 1, memo);
        } else {
            int includeItem = values[n - 1] + knapsackMemo(capacity - weights[n - 1], weights, values, n - 1, memo);
            int excludeItem = knapsackMemo(capacity, weights, values, n - 1, memo);
            memo[n][capacity] = max(includeItem, excludeItem);
        }

        return memo[n][capacity];
    }

    int knapsack(int capacity, int weights[], int values[], int n) {
        // Initialize memo table with -1
        vector<vector<int>> memo(n + 1, vector<int>(capacity + 1, -1));

        // Call memoized helper
        return knapsackMemo(capacity, weights, values, n, memo);
    }
};

// Example usage
int main() {
    Solution solution;
    int weights[] = {2, 3, 4};
    int values[] = {4, 5, 6};
    int capacity = 5;
    int n = sizeof(weights) / sizeof(weights[0]);
    cout << "Maximum value: " << solution.knapsack(capacity, weights, values, n) << endl;
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


class Solution {
    public int knapsack(int W, int[] weights, int[] values, int n) {
        // Initialize memo table with -1
        int[][] memo = new int[n + 1][W + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(memo[i], -1);
        }

        return helper(W, weights, values, n, memo);
    }

    private int helper(int W, int[] weights, int[] values, int n, int[][] memo) {
        // Base Case: No items left or capacity exhausted
        if (n == 0 || W == 0) {
            return 0;
        }

        // If the result for this subproblem is already computed
        if (memo[n][W] != -1) {
            return memo[n][W];
        }

        // If the current item's weight exceeds the remaining capacity
        if (weights[n - 1] > W) {
            memo[n][W] = helper(W, weights, values, n - 1, memo);
        } else {
            int includeItem = values[n - 1] + helper(W - weights[n - 1], weights, values, n - 1, memo);
            int excludeItem = helper(W, weights, values, n - 1, memo);
            memo[n][W] = Math.max(includeItem, excludeItem);
        }

        return memo[n][W];
    }

    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] weights = {2, 3, 4};
        int[] values = {4, 5, 6};
        int capacity = 5;
        System.out.println("Maximum value: " + solution.knapsack(capacity, weights, values, weights.length));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class Solution:
    def knapsack(self, W, weights, values, n):
        # Initialize memo table with -1
        memo = [[-1 for _ in range(W + 1)] for _ in range(n + 1)]

        def helper(W, weights, values, n):
            # Base Case: No items left or capacity exhausted
            if n == 0 or W == 0:
                return 0

            # If the result for this subproblem is already computed
            if memo[n][W] != -1:
                return memo[n][W]

            # If the current item's weight exceeds the remaining capacity
            if weights[n - 1] > W:
                memo[n][W] = helper(W, weights, values, n - 1)
            else:
                include_item = values[n - 1] + helper(W - weights[n - 1], weights, values, n - 1)
                exclude_item = helper(W, weights, values, n - 1)
                memo[n][W] = max(include_item, exclude_item)

            return memo[n][W]

        return helper(W, weights, values, n)


# Example usage:
solution = Solution()
weights = [2, 3, 4]
values = [4, 5, 6]
capacity = 5
print("Maximum value:", solution.knapsack(capacity, weights, values, len(weights)))

Complexity

⏰ Time complexity: O(n*W). Filling the memoisation table involves O(n × W) operations, where n is the number of items and W is the knapsack capacity.
🧺 Space complexity: O(n*W). The memoisation table requires O(n × W) memory.

Method 3 - Bottom-up DP

In the bottom-up DP approach, the goal is to iteratively calculate the maximum value obtainable for each weight from 1 to W and for each item from 1 to n. This approach eliminates recursion and uses a 2-dimensional table to store intermediate results.

Intuition

To find the recurrence relation, consider this: for each item i and capacity W:

Each item is either selected or not. The maximum value for a given weight W can be obtained by:
- Including the item: If its weight wi allows room in the knapsack (W - wi), add its value vi to the value from the remaining weight (W - wi, considering up to item i-1).
- Excluding the item: Retain the value obtained for weight W considering up to item i-1.

Formally, this recurrence is expressed as:

1

value(W, i) = max( value(W-wi, i-1) + vi, value(W, i-1) )

To compute the result for value(W, n) (knapsack of capacity W with all n items), we need to calculate values for all combinations of:
- Total weights from 1 to W.
- Items from 1 to n.

Pseudocode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


Knapsack(W, weights, values, n):
    Initialize value[i][j] = 0 for all i and j  // Base condition
    
    for i from 1 to n:
        for w from 1 to W:
            value[w][i] = value[w][i-1] // Exclude the item
            
            if weights[i-1] <= w: // Item can fit
                val = value[w-weights[i-1]][i-1] + values[i-1]
                value[w][i] = max(value[w][i], val) // Include the item
                
    return value[W][n]  // Result (maximum value for capacity W using n items)

Base Condition

If there are zero items (i = 0), the value is zero for any weight:
1

value(W, 0) = 0
If the capacity is zero (W = 0), the value is zero for any number of items:
1

value(0, i) = 0

Intuition

n represents the number of items being considered.
W represents the current capacity of the knapsack.

If a value for memo[n][W] is computed, it is reused instead of recalculating the result.

Recursive Relation Revisited

The recursive relation remains the same:

Weight exceeds capacity: If the item’s weight (wt[n]) exceeds the current capacity W, exclude it:
1

memo[n][W] = memo[n-1][W]
Weight fits: If the item can fit, compute the maximum value of including or excluding the item:
1

memo[n][W] = max(memo[n-1][W], memo[n-1][W-wt[n]] + val[n])

Base Conditions

memo[0][W] = 0 → No items, value is 0.
memo[n][0] = 0 → No capacity, value is 0.

Dry Run

Consider 4 items:

(w1, v1) = (6, 30)
(w2, v2) = (3, 14)
(w3, v3) = (4, 16)
(w4, v4) = (2, 9)

Total capacity W = 10.

Here are step by step explanation:

Start with a 2D table where:
- Rows represent items.
- Columns represent weights from 0 to W.
For each item and weight, compute whether to include or exclude the item. For example:
- value[2][10] (considering 2 items, knapsack capacity = 10) = max(30, 14 + value[7]) = 44.
- Final result value[10][4] is computed as:
  1 2 3
  
  value[10, 4] = max(value[8, 3] + 9, value[10, 3]) = max(46, 30) = 46

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


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

class Solution {
public:
    int knapsack(int capacity, vector<int>& weights, vector<int>& values, int n) {
        // Initialize DP table
        vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

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

        return dp[n][capacity]; // Maximum value for capacity W with n items
    }
};

// Example usage
int main() {
    Solution solution;
    vector<int> weights = {6, 3, 4, 2};
    vector<int> values = {30, 14, 16, 9};
    int capacity = 10;
    cout << "Maximum value: " << solution.knapsack(capacity, weights, values, weights.size()) << endl;
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
    public int knapsack(int W, int[] weights, int[] values, int n) {
        // Initialize DP table
        int[][] dp = new int[n + 1][W + 1];

        // Fill DP table
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= W; w++) {
                dp[i][w] = dp[i - 1][w]; // Exclude the item
                if (weights[i - 1] <= w) { // Include the item if it fits
                    dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                }
            }
        }

        return dp[n][W]; // Maximum value for capacity W with n items
    }

    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] weights = {6, 3, 4, 2};
        int[] values = {30, 14, 16, 9};
        int capacity = 10;
        System.out.println("Maximum value: " + solution.knapsack(capacity, weights, values, weights.length));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def knapsack(self, W, weights, values, n):
        # Initialize DP table (value[i][j]) with zeros
        dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]

        # Fill the DP table
        for i in range(1, n + 1):
            for w in range(1, W + 1):
                dp[i][w] = dp[i - 1][w]  # Exclude the item
                if weights[i - 1] <= w:  # Include the item if it fits
                    dp[i][w] = max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])

        return dp[n][W]  # Maximum value for capacity W with n items
 
# Example usage:
solution = Solution()
weights = [6, 3, 4, 2]
values = [30, 14, 16, 9]
capacity = 10
print("Maximum value:", solution.knapsack(capacity, weights, values, len(weights)))

Complexity

⏰ Time complexity: O(n*W). Filling the table involves n rows (number of items) and W columns (capacity). Each cell takes constant time.
🧺 Space complexity: O(n*W). A 2D table (value[n][W]) is required

Problem#

Examples#

Example 1#

Example 2#

Variation#

Solution#

Method 1 - Recursion#

Recursive Structure#

Code#

Complexity#

Method 2 - Top-down DP using memoized solution#

Intuition#

Recursive Relation Revisited#

Base Conditions#

Code#

Complexity#

Method 3 - Bottom-up DP#

Intuition#

Pseudocode#

Base Condition#

Intuition#

Recursive Relation Revisited#

Base Conditions#

Dry Run#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Variation

Solution

Method 1 - Recursion

Recursive Structure

Code

Complexity

Method 2 - Top-down DP using memoized solution

Intuition

Recursive Relation Revisited

Base Conditions

Code

Complexity

Method 3 - Bottom-up DP

Intuition

Pseudocode

Base Condition

Intuition

Recursive Relation Revisited

Base Conditions

Dry Run

Code

Complexity