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 <= 300We 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$.
Java
C++
Go
TypeScript
Rust
Practice Maximum Weight in Two Bags with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor