Problem Description

You have an integer array weights representing the weights of different items, and two integers w1 and w2 representing the maximum weight capacities of two bags.

Your task is to pack items into these two bags following these rules:

• Each item can be placed in at most one bag (or not placed at all)
• Bag 1 can hold items with a total weight of at most w1
• Bag 2 can hold items with a total weight of at most w2

The goal is to find the maximum total weight that can be packed into both bags combined.

For example, if you have items with weights [1, 2, 3] and bags with capacities w1 = 3 and w2 = 4, you could:

• Put item with weight 3 in bag 1 (total: 3)
• Put items with weights 1 and 2 in bag 2 (total: 3)
• This gives a maximum total weight of 6

The problem is essentially a variant of the knapsack problem where you have two knapsacks instead of one, and each item can only be used once across both bags.

Intuition

When we see this problem, we need to think about the decisions we make for each item. For every item, we have three choices:

1. Don't take the item at all
2. Put it in bag 1 (if it fits)
3. Put it in bag 2 (if it fits)

This naturally leads us to think about dynamic programming, where we track the state of both bags as we consider items one by one.

The key insight is that we need to keep track of the remaining capacities of both bags simultaneously. This is different from the classic knapsack problem where we only track one capacity. We can think of our state as (remaining capacity of bag 1, remaining capacity of bag 2).

For each state f[j][k], we store the maximum weight we can achieve when bag 1 has capacity j and bag 2 has capacity k. When we consider adding a new item with weight x:

• If we put it in bag 1, we transition from state f[j-x][k] to f[j][k] (adding weight x)
• If we put it in bag 2, we transition from state f[j][k-x] to f[j][k] (adding weight x)
• If we skip it, we keep the current best value at f[j][k]

We process items one by one, updating our DP table. To avoid using the same item multiple times in one iteration, we traverse the capacities in reverse order (from high to low). This ensures that when we update f[j][k], we're using the values from the previous iteration, not the current one.

The final answer is f[w1][w2], which represents the maximum weight we can achieve when both bags are at their full capacities.

Solution Approach

We implement a 2D dynamic programming solution where f[j][k] represents the maximum weight we can achieve with bag 1 having capacity j and bag 2 having capacity k.

Initialization: We create a 2D array f with dimensions (w1 + 1) × (w2 + 1), initialized with zeros. This represents that initially, no items are placed in either bag.

f = [[0] * (w2 + 1) for _ in range(w1 + 1)]

Processing Items: For each item with weight x in the weights array, we update our DP table. We iterate through all possible capacities of both bags in reverse order:

for x in weights:
    for j in range(w1, -1, -1):
        for k in range(w2, -1, -1):

The reverse traversal is crucial - it ensures we don't use the same item multiple times. When we update f[j][k], we're using values from the previous iteration (before considering the current item).

State Transitions: For each state (j, k), we have three options:

1. Skip the item: Keep f[j][k] as is
2. Put item in bag 1: If x <= j, update f[j][k] = max(f[j][k], f[j - x][k] + x)
3. Put item in bag 2: If x <= k, update f[j][k] = max(f[j][k], f[j][k - x] + x)

if x <= j:
    f[j][k] = max(f[j][k], f[j - x][k] + x)
if x <= k:
    f[j][k] = max(f[j][k], f[j][k - x] + x)

Space Optimization: Notice that we're using a 2D array instead of 3D. This is because when processing item i, we only need information from item i-1. By traversing in reverse order, we can reuse the same 2D array, reducing space complexity from O(n × w1 × w2) to O(w1 × w2).

Final Result: After processing all items, f[w1][w2] contains the maximum weight that can be packed into both bags.

The time complexity is O(n × w1 × w2) where n is the number of items, and the space complexity is O(w1 × w2).

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• weights = [2, 3, 4]
• w1 = 5 (bag 1 capacity)
• w2 = 3 (bag 2 capacity)

Step 1: Initialize DP Table We create a 2D array f of size (6 × 4) initialized with zeros:

    k=0  k=1  k=2  k=3
j=0  0    0    0    0
j=1  0    0    0    0
j=2  0    0    0    0
j=3  0    0    0    0
j=4  0    0    0    0
j=5  0    0    0    0

Step 2: Process First Item (weight = 2) We traverse in reverse order. For each valid position:

• At f[5][3]: Can put in bag 1 → f[5][3] = max(0, f[3][3] + 2) = 2
• At f[5][3]: Can put in bag 2 → f[5][3] = max(2, f[5][1] + 2) = 2
• At f[2][3]: Can put in bag 1 → f[2][3] = max(0, f[0][3] + 2) = 2
• Similar updates for other valid positions...

After processing item 1:

    k=0  k=1  k=2  k=3
j=0  0    0    0    0
j=1  0    0    0    0
j=2  0    0    2    2
j=3  0    0    2    2
j=4  0    0    2    2
j=5  0    0    2    2

Step 3: Process Second Item (weight = 3) Key updates:

• At f[5][3]: Can put in bag 1 → f[5][3] = max(2, f[2][3] + 3) = 5
• At f[5][3]: Can put in bag 2 → f[5][3] = max(5, f[5][0] + 3) = 5
• At f[3][3]: Can put in bag 1 → f[3][3] = max(2, f[0][3] + 3) = 3

After processing item 2:

    k=0  k=1  k=2  k=3
j=0  0    0    0    0
j=1  0    0    0    0
j=2  0    0    2    2
j=3  0    0    2    3
j=4  0    0    2    3
j=5  0    0    2    5

Step 4: Process Third Item (weight = 4) Key updates:

• At f[5][3]: Can put in bag 1 → f[5][3] = max(5, f[1][3] + 4) = 5
• At f[4][3]: Can put in bag 1 → f[4][3] = max(3, f[0][3] + 4) = 4

After processing item 3:

    k=0  k=1  k=2  k=3
j=0  0    0    0    0
j=1  0    0    0    0
j=2  0    0    2    2
j=3  0    0    2    3
j=4  0    0    2    4
j=5  0    0    2    5

Final Result: f[5][3] = 5 is our answer.

This means we can pack a maximum total weight of 5. One optimal solution is:

• Put item with weight 2 in bag 2 (uses 2 out of 3 capacity)
• Put item with weight 3 in bag 1 (uses 3 out of 5 capacity)
• Skip item with weight 4
• Total weight = 2 + 3 = 5

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × w1 × w2)

The algorithm iterates through each weight in the weights array (n elements), and for each weight, it performs nested iterations through all possible capacities from w1 to 0 and w2 to 0. This results in n × (w1 + 1) × (w2 + 1) operations, which simplifies to O(n × w1 × w2).

Space Complexity: O(w1 × w2)

The algorithm uses a 2D array f with dimensions (w1 + 1) × (w2 + 1) to store the dynamic programming states. No other data structures scale with the input size, so the space complexity is O(w1 × w2).

Common Pitfalls

1. Incorrect Traversal Order - Using Forward Iteration

One of the most common mistakes is iterating through capacities in forward order instead of reverse order. This leads to using the same item multiple times.

Incorrect Code:

# WRONG - Forward iteration allows reusing items
for weight in weights:
    for capacity1 in range(w1 + 1):  # Forward order
        for capacity2 in range(w2 + 1):  # Forward order
            if weight <= capacity1:
                dp[capacity1][capacity2] = max(
                    dp[capacity1][capacity2],
                    dp[capacity1 - weight][capacity2] + weight
                )
            if weight <= capacity2:
                dp[capacity1][capacity2] = max(
                    dp[capacity1][capacity2],
                    dp[capacity1][capacity2 - weight] + weight
                )

Why it's wrong: When we update dp[capacity1][capacity2], we might use dp[capacity1 - weight][capacity2] which was already updated in the current iteration (considering the same item). This effectively allows using the same item multiple times.

Solution: Always use reverse iteration when dealing with 0/1 knapsack variants:

for capacity1 in range(w1, -1, -1):  # Reverse order
    for capacity2 in range(w2, -1, -1):  # Reverse order

2. Updating Both Bags in Separate If-Statements Without Proper Max Comparison

Another subtle issue occurs when the two if-statements for bag updates aren't properly structured, potentially overwriting a better solution.

Problematic Pattern:

# Potentially problematic if not careful with max comparisons
if weight <= capacity1:
    dp[capacity1][capacity2] = dp[capacity1 - weight][capacity2] + weight  # Missing max()
if weight <= capacity2:
    dp[capacity1][capacity2] = dp[capacity1][capacity2 - weight] + weight  # Overwrites!

Solution: Always use max() to preserve the best solution found so far:

if weight <= capacity1:
    dp[capacity1][capacity2] = max(
        dp[capacity1][capacity2],
        dp[capacity1 - weight][capacity2] + weight
    )
if weight <= capacity2:
    dp[capacity1][capacity2] = max(
        dp[capacity1][capacity2],  # Preserves previous best
        dp[capacity1][capacity2 - weight] + weight
    )

3. Using 3D DP Array When 2D Suffices

While not incorrect, using a 3D array dp[i][j][k] where i represents items considered is unnecessary and wastes memory.

Space-Inefficient Approach:

# Unnecessary 3D array
dp = [[[0] * (w2 + 1) for _ in range(w1 + 1)] for _ in range(len(weights) + 1)]

Solution: Since we only need the previous state when processing each item, a 2D array with reverse iteration is sufficient, reducing space complexity from O(n × w1 × w2) to O(w1 × w2).