Skip to main content
Talentd

Maximum Weight in Two Bags - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDynamic Programming10 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem 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.

Solution

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$.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force AssignmentO(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

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Maximum Weight in Two Bags with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays