You are given an integer array weights and two integers w1 and w2 representing the maximum capacities of two bags.
Each item may be placed in at most one bag such that:
w1 total weight.w2 total weight.Return the maximum total weight that can be packed into the two bags.
Example 1:
Input: weights = [1,4,3,2], w1 = 5, w2 = 4
Output: 9
Explanation:
weights[2] = 3 and weights[3] = 2 as 3 + 2 = 5 <= w1weights[1] = 4 as 4 <= w25 + 4 = 9Example 2:
Input: weights = [3,6,4,8], w1 = 9, w2 = 7
Output: 15
Explanation:
weights[3] = 8 as 8 <= w1weights[0] = 3 and weights[2] = 4 as 3 + 4 = 7 <= w28 + 7 = 15Example 3:
Input: weights = [5,7], w1 = 2, w2 = 3
Output: 0
Explanation:
No weight fits in either bag, thus the answer is 0.
Constraints:
1 <= weights.length <= 1001 <= weights[i] <= 1001 <= w1, w2 <= 300Problem Overview: You are given items with weights and two bags with fixed capacities. Each item can go into bag 1, bag 2, or be skipped. The goal is to maximize the total weight placed into the two bags without exceeding either bag’s capacity.
Approach 1: Brute Force Enumeration (Exponential Time)
The most direct strategy is to try every assignment for each item: place it in bag 1, place it in bag 2, or skip it. A recursive search explores all combinations and tracks remaining capacities. This guarantees the optimal result but requires checking up to 3^n possibilities. Time complexity is O(3^n) and space complexity is O(n) for recursion depth. This approach works only for very small inputs and mainly helps you understand the state transitions before optimizing.
Approach 2: Dynamic Programming with Two Capacities (Optimal)
This problem maps directly to a two-dimensional knapsack variant. Define dp[i][c1][c2] as the maximum weight achievable using the first i items with c1 capacity remaining in bag 1 and c2 capacity remaining in bag 2. For each item, you iterate through capacities and choose among three actions: skip it, place it in bag 1 (if weight ≤ c1), or place it in bag 2 (if weight ≤ c2). The transition takes the best of these options.
To reduce memory, you typically keep only the current and previous item states or compress the item dimension entirely, resulting in a 2D DP table. The algorithm iterates through all items and capacity combinations using nested loops. Time complexity is O(n × C1 × C2) and space complexity is O(C1 × C2). This approach is standard for multi-container knapsack problems and relies on techniques from dynamic programming over a weight state space.
Recommended for interviews: Interviewers expect the dynamic programming solution. Showing the brute force reasoning demonstrates that you understand the decision tree for each item. Converting that reasoning into a DP state with two capacities shows real problem‑solving skill. If you recognize the relationship to classic knapsack problems over an array of weights and model the two capacity constraints correctly, you reach the optimal solution quickly.
We define f[i][j][k] to represent the maximum total weight when placing the first i items into two bags, where bag 1 has a maximum capacity of j and bag 2 has a maximum capacity of k. Initially, f[0][j][k] = 0, indicating that no items can be placed in the bags.
The state transition equation is:
$
f[i][j][k] = max(f[i-1][j][k], f[i-1][j-w_i][k], f[i-1][j][k-w_i]) \quad (w_i leq j or w_i leq k)
where w_i represents the weight of the i-th item.
The final answer is f[n][w1][w2], where n is the number of items.
We notice that the state transition equation only depends on the previous layer's state, so we can compress the three-dimensional DP array into a two-dimensional DP array. When enumerating j and k, we use reverse traversal.
Time complexity O(n times w1 times w2), space complexity O(w1 times w2). Where n is the length of the array weights$.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Assignment | O(3^n) | O(n) | Conceptual baseline to understand choices for each item |
| Dynamic Programming (3D State) | O(n × C1 × C2) | O(n × C1 × C2) | Clear formulation when learning multi-bag knapsack |
| Dynamic Programming (2D Optimized) | O(n × C1 × C2) | O(C1 × C2) | Preferred solution in practice and interviews |
Practice Maximum Weight in Two Bags with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor