Problem

Given N items with corresponding weights (w1, w2, ... wn) and values (v1, v2, ... vn), along with the total capacity weight W for a knapsack, determine the maximum value that can be achieved by filling the knapsack. Here, each item can be used any number of times, making it an unbounded knapsack problem. The goal is to maximise the total value of items selected such that their total weight does not exceed W.

Examples

Example 1

1
2
3
4
5
6

Input:  
Weights = [2, 4, 6], Values = [8, 16, 24], Capacity = 10  
Output:  
Maximum value = 40  
Explanation:  
- Item 1 can be taken 5 times (2 × 5 = 10 weight) → Total value = 40

Example 2

1
2
3
4
5
6
7

Input:  
Weights = [1, 3, 4], Values = [10, 30, 50], Capacity = 7  
Output:  
Maximum value = 90  
Explanation:  
- Item 1 is taken once (1 weight, 10 value).  
- Item 2 is taken twice (3 × 2 = 6 weight, 60 value) → Total value = 90

Variations

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:

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

This problem is similar to Coin Change 3 - Coin Change with Fewest/Minimum Number of Coins. There the amount is like capacity, and coins are like items of different value.

Method 1 - Recursion

Here are the steps:

  1. Base Case: Stop recursion when no items are left (n == 0) or when the knapsack capacity is zero (W == 0).
  2. Check weight constraint: If the weight of the current item exceeds the remaining capacity, skip the item and move to the next one.
  3. Recursive Choice:
    • Include current item: Take the item, decrease the capacity by its weight, and add its value to the result of the recursive call.
    • Exclude current item: Skip the item and make a recursive call for the remaining items.
    • Return the maximum value from the two choices.

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 itemCount) {
        // Base Case: No items left or capacity is zero
        if (itemCount == 0 || capacity == 0)
            return 0;

        // If current item's weight exceeds the remaining capacity
        if (weights[itemCount - 1] > capacity)
            return knapsack(capacity, weights, values, itemCount - 1);

        // Calculate the maximum value by including or excluding the current item
        else {
            int includeItem = values[itemCount - 1] + knapsack(capacity - weights[itemCount - 1], weights, values, itemCount);
            int excludeItem = knapsack(capacity, weights, values, itemCount - 1);
            return max(includeItem, excludeItem);
        }
    }
};

// Example usage
int main() {
    Solution solution;
    int weights[] = {2, 4, 6};
    int values[] = {8, 16, 24};
    int capacity = 10;
    int itemCount = sizeof(weights) / sizeof(weights[0]);
    cout << "Maximum value: " << solution.knapsack(capacity, weights, values, itemCount) << 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

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

        // If current item's weight exceeds the remaining capacity
        if (weights[itemCount - 1] > capacity)
            return knapsack(capacity, weights, values, itemCount - 1);

        // Calculate the maximum value by including or excluding the current item
        else {
            int includeItem = values[itemCount - 1] + knapsack(capacity - weights[itemCount - 1], weights, values, itemCount);
            int excludeItem = knapsack(capacity, weights, values, itemCount - 1);
            return Math.max(includeItem, excludeItem);
        }
    }

    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] weights = {2, 4, 6};
        int[] values = {8, 16, 24};
        int capacity = 10;
        int itemCount = weights.length;
        System.out.println("Maximum value: " + solution.knapsack(capacity, weights, values, itemCount));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

        # If current item's weight exceeds the remaining capacity
        if weights[n - 1] > W:
            return self.knapSack(W, weights, values, n - 1)

        # Otherwise, calculate the maximum value by including or excluding the current item
        else:
            include_current = values[n - 1] + self.knapSack(W - weights[n - 1], weights, values, n)
            exclude_current = self.knapSack(W, weights, values, n - 1)
            return max(include_current, exclude_current)

# Example usage:
solution = Solution()
weights = [2, 4, 6]
values = [8, 16, 24]
capacity = 10
print("Maximum value:", solution.knapSack(capacity, weights, values, len(weights)))

Complexity

  • ⏰ Time complexity: O(2^n), where n is the number of items. For each item, either include it or exclude it, resulting in 2^n recursive calls.
  • 🧺 Space complexity: O(n) due to recursion depth.

Method 2 - Top-down DP with memoization

Memoization adds a cache to store previously computed results of subproblems. This avoids redundant computations, making the recursive solution more efficient.

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
47
48

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

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

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

        // If current item's weight exceeds the remaining capacity
        if (weights[itemCount - 1] > capacity) {
            memo[itemCount][capacity] = knapsackMemo(capacity, weights, values, itemCount - 1, memo);
        } else {
            // Calculate the maximum value by including or excluding the current item
            int includeItem = values[itemCount - 1] + knapsackMemo(capacity - weights[itemCount - 1], weights, values, itemCount, memo);
            int excludeItem = knapsackMemo(capacity, weights, values, itemCount - 1, memo);
            memo[itemCount][capacity] = max(includeItem, excludeItem);
        }

        return memo[itemCount][capacity];
    }

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

        // Call the helper function
        return knapsackMemo(capacity, weights, values, itemCount, memo);
    }
};

// Example usage
int main() {
    Solution solution;
    int weights[] = {2, 4, 6};
    int values[] = {8, 16, 24};
    int capacity = 10;
    int itemCount = sizeof(weights) / sizeof(weights[0]);
    cout << "Maximum value: " << solution.knapsack(capacity, weights, values, itemCount) << 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
44

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

        return knapsackMemo(capacity, weights, values, itemCount, memo);
    }

    private int knapsackMemo(int capacity, int[] weights, int[] values, int itemCount, int[][] memo) {
        // Base Case: No items left or capacity is zero
        if (itemCount == 0 || capacity == 0) {
            return 0;
        }

        // If result for this subproblem is already computed, return it
        if (memo[itemCount][capacity] != -1) {
            return memo[itemCount][capacity];
        }

        // If current item's weight exceeds the remaining capacity
        if (weights[itemCount - 1] > capacity) {
            memo[itemCount][capacity] = knapsackMemo(capacity, weights, values, itemCount - 1, memo);
        } else {
            // Calculate the maximum value by including or excluding the current item
            int includeItem = values[itemCount - 1] + knapsackMemo(capacity - weights[itemCount - 1], weights, values, itemCount, memo);
            int excludeItem = knapsackMemo(capacity, weights, values, itemCount - 1, memo);
            memo[itemCount][capacity] = Math.max(includeItem, excludeItem);
        }

        return memo[itemCount][capacity];
    }

    // Example Usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] weights = {2, 4, 6};
        int[] values = {8, 16, 24};
        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
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

        def knapsackMemo(capacity, weights, values, itemCount, memo):
            # Base Case: No items left or capacity is zero
            if itemCount == 0 or capacity == 0:
                return 0

            # If result for this subproblem is already computed, return it
            if memo[itemCount][capacity] != -1:
                return memo[itemCount][capacity]

            # If current item's weight exceeds the remaining capacity
            if weights[itemCount - 1] > capacity:
                memo[itemCount][capacity] = knapsackMemo(capacity, weights, values, itemCount - 1, memo)
            else:
                # Calculate the maximum value by including or excluding the current item
                includeItem = values[itemCount - 1] + knapsackMemo(capacity - weights[itemCount - 1], weights, values, itemCount, memo)
                excludeItem = knapsackMemo(capacity, weights, values, itemCount - 1, memo)
                memo[itemCount][capacity] = max(includeItem, excludeItem)

            return memo[itemCount][capacity]

        return knapsackMemo(capacity, weights, values, itemCount, memo)


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

Complexity

  • ⏰ Time complexity: O(n*W). Each subproblem is solved once and stored in the memo table.
  • 🧺 Space complexity: O(n*W). Space is used for the memo table. Additionally, recursive calls use stack space proportional to itemCount.

Method 3 - Bottom-up DP with tabulation

Now, lets solve it using bottom-up dynamic programming approach. The relationship between the subproblems can be expressed as:

1

value(w) = max {value(w - wi) + vi} for all i such that wi ≤ w

This means that to compute the maximum value for capacity w, we consider taking the current item of weight wi multiple times (if allowed) and add its value vi to the maximum value of the remaining capacity (w - wi). We calculate the optimal value by trying this for all items.

Pseudocode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

KnapsackUnbounded(W, weights, values, n)
    Initialize value[0...W] ← 0  // DP array to store max values for each capacity
    
    for w from 1 to W:
        maxValue ← 0
        for i from 1 to n:
            if weights[i] ≤ w:
                maxValue = max(maxValue, value[w - weights[i]] + values[i])
        value[w] ← maxValue
    
    return value[W]  // Maximum value for full capacity

Approach

Here are the steps:

  • Base Case: The maximum value for a capacity of 0 (value[0]) is 0 since we cannot include any items.
  • Iterative Calculation: For each capacity w, we iterate through all items and compute the maximum value by including the current item multiple times (if possible) and comparing values from different combinations.
  • Final Value: The result (value[W]) gives the maximum value achievable for the given knapsack capacity W.

Dry Run

Consider 4 items with weights and values:

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

Steps:

  1. Weight 0: No items can be included → value[0] = 0.
  2. Weight 1: No items can be included → value[1] = 0.
  3. Weight 2: Only w4 fits → value[2] = 9.
  4. Weight 3: Either exclude w4 or include w2. Choose max(value[2], 0 + v2) → value[3] = 14.
  5. Weight 4: Compare:
    • value[2] + v4 = 18
    • value[3] + v1 = 14
    • value[0] + v3 = 16 Choose maximum → value[4] = 18.

Proceed similarly for higher weights. For the total capacity of 48, the maximum value is 30 + 2 × 9 = 48.

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>
#include <algorithm>
using namespace std;

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

        // Fill DP array
        for (int w = 1; w <= capacity; ++w) {
            for (int i = 0; i < itemCount; ++i) {
                if (weights[i] <= w) {
                    dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
                }
            }
        }

        return dp[capacity];
    }
};

// Example usage
int main() {
    Solution solution;
    vector<int> weights = {6, 3, 4, 2};
    vector<int> values = {30, 14, 16, 9};
    int capacity = 48;
    cout << "Maximum value: " << solution.unboundedKnapsack(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

class Solution {
    public int unboundedKnapsack(int capacity, int[] weights, int[] values, int itemCount) {
        // Initialize DP array
        int[] dp = new int[capacity + 1];

        // Fill DP array
        for (int w = 1; w <= capacity; ++w) {
            for (int i = 0; i < itemCount; ++i) {
                if (weights[i] <= w) {
                    dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
                }
            }
        }

        return dp[capacity];
    }

    // 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 = 48;
        System.out.println("Maximum value: " + solution.unboundedKnapsack(capacity, weights, values, weights.length));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def unboundedKnapsack(self, capacity, weights, values, itemCount):
        # Initialize DP array
        dp = [0] * (capacity + 1)

        # Fill DP array
        for w in range(1, capacity + 1):
            for i in range(itemCount):
                if weights[i] <= w:
                    dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

        return dp[capacity]

# Example usage:
solution = Solution()
weights = [6, 3, 4, 2]
values = [30, 14, 16, 9]
capacity = 48
print("Maximum value:", solution.unboundedKnapsack(capacity, weights, values, len(weights)))

Complexity

  • ⏰ Time complexity: O(n*W) as filling the DP array requires iterating through all capacities (W) and all items (n).
  • 🧺 Space complexity: O(W) as e require a DP array of size W + 1 to store results for all capacities.