Is Maximum Weight in Two Bags easy or hard?

Maximum Weight in Two Bags is typically considered a medium-level dynamic programming problem. The main challenge is recognizing that it extends the classic knapsack problem to two capacity dimensions and designing the correct DP state and transitions.

Maximum Weight in Two Bags Python/Java solution

Implement the DP table as a 2D array where dp[c1][c2] represents the best weight achievable with those capacities remaining. Iterate through each item and update states in reverse capacity order to avoid overwriting needed values. The same logic works in Python, Java, C++, Go, TypeScript, and Rust.

How to solve Maximum Weight in Two Bags in O(n)?

A true O(n) solution is not possible because the algorithm must consider capacity constraints for both bags. The best known approach uses dynamic programming over the capacity states, giving O(n × C1 × C2) time. This is essentially a two‑knapsack variant of the classic knapsack DP.

What is the best approach for Maximum Weight in Two Bags?

The best approach is dynamic programming with two capacity dimensions. You track the maximum achievable weight for every combination of remaining capacity in bag 1 and bag 2. This converts the exponential search into a structured state transition with O(n × C1 × C2) time and O(C1 × C2) space.

Is Maximum Weight in Two Bags asked at Google/Amazon/Meta?

Multi‑knapsack and capacity allocation problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of the two‑bag or multiple‑bag knapsack test a candidate’s ability to design dynamic programming states and manage multiple constraints efficiently.

What data structure is used in Maximum Weight in Two Bags?

The core data structure is a dynamic programming table, typically a 2D array indexed by the remaining capacity of the two bags. Each cell stores the maximum total weight achievable for that capacity pair. The input itself is usually processed as an array of item weights.

What is the time complexity of Maximum Weight in Two Bags?

The optimal dynamic programming solution runs in O(n × C1 × C2) time, where n is the number of items and C1 and C2 are the capacities of the two bags. Each item is processed across all capacity combinations. Space complexity can be reduced to O(C1 × C2) using a compressed DP table.

Description Hints 2 Solution

3647. Maximum Weight in Two Bags

Medium58.3% acceptancePremium elsewhere, free here

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:

Bag 1 holds at most w1 total weight.
Bag 2 holds at most 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:

Bag 1: Place weights[2] = 3 and weights[3] = 2 as 3 + 2 = 5 <= w1
Bag 2: Place weights[1] = 4 as 4 <= w2
Total weight: 5 + 4 = 9

Example 2:

Input: weights = [3,6,4,8], w1 = 9, w2 = 7

Output: 15

Explanation:

Bag 1: Place weights[3] = 8 as 8 <= w1
Bag 2: Place weights[0] = 3 and weights[2] = 4 as 3 + 4 = 7 <= w2
Total weight: 8 + 7 = 15

Example 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 <= 100
1 <= weights[i] <= 100
1 <= w1, w2 <= 300

Topics

Array Dynamic Programming

Hints open one at a time

Hint 1

Use dynamic programming.

Hint 2

Let dp[i][j] be the maximum total weight that can be held in the two bags when their current weights (or used capacities) are i and j, respectively.

Still stuck?Read the written solution.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,4,3,2]
5
4

Input

[3,6,4,8]
9
7

Input

[5,7]
2
3

Your code is saved on this device.Solution