LeetCode 3647 - Maximum Weight in Two Bags

This problem asks us to distribute a set of items, each with a given weight, into two separate bags with fixed capacity limits, in order to maximize the total weight placed across both bags.

leetcodemediumarraydynamic-programming

LeetCode Problem 3647

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem asks us to distribute a set of items, each with a given weight, into two separate bags with fixed capacity limits, in order to maximize the total weight placed across both bags.

Each item in the input array weights can be used at most once, and for each item we must decide one of three possible actions: place it in bag 1, place it in bag 2, or skip it entirely. Bag 1 can hold items whose total weight does not exceed w1, and bag 2 has an independent capacity limit w2. The goal is to maximize the sum of weights successfully placed in either bag.

The output is a single integer representing the maximum achievable total packed weight across both bags.

The constraints indicate that the number of items is at most 100, and both capacities are at most 300. This strongly suggests that a dynamic programming solution with a state depending on both capacities is feasible, since a cubic bound around 100 × 300 × 300 is acceptable.

Important edge cases include situations where no items can fit into either bag, cases where all items fit into one bag but not both, and cases where greedy placement would fail due to capacity tradeoffs between the two bags. Another key observation is that item order does not matter, only assignment decisions do.

Approaches

The brute-force approach considers every possible assignment of each item into one of three states: bag 1, bag 2, or unused. This leads to 3^n possibilities, which becomes infeasible for n up to 100. While correct in theory, it is computationally impossible due to exponential growth.

The optimal solution uses dynamic programming with a two-dimensional state representing remaining or used capacity in both bags. The key insight is that each decision affects two independent capacity dimensions, so we track the best achievable weight for every possible pair of capacities. Each item transitions the DP state by either skipping it or placing it in one of the two bags if capacity allows.

Approach Time Complexity Space Complexity Notes
Brute Force O(3^n) O(n) Try all assignments of each item into bag1, bag2, or skip
Optimal DP O(n · w1 · w2) O(w1 · w2) 2D knapsack-style DP over both bag capacities

Algorithm Walkthrough

The optimal solution is based on a two-dimensional knapsack dynamic programming formulation, where each dimension corresponds to one bag’s remaining capacity.

  1. We define a DP table dp[i][j] as the maximum total weight achievable using any subset of processed items such that bag 1 has used capacity i and bag 2 has used capacity j. This formulation allows us to capture all valid assignment combinations.
  2. We initialize the DP table with all zeros because initially, with no items considered, the maximum weight achievable is zero regardless of capacity usage.
  3. We iterate through each item in the weights array. For each item with weight w, we consider how it can be assigned into the current DP state.
  4. For each item, we update the DP table in reverse order of capacities, iterating i from w1 down to 0 and j from w2 down to 0. This reverse traversal ensures that each item is only used once, preventing overwriting states that are needed for correct transitions.
  5. For each capacity pair (i, j), we consider three possibilities: we skip the item and retain the current best value, we place the item into bag 1 if i >= w, or we place it into bag 2 if j >= w. We update the state with the maximum of these valid options.
  6. After processing all items, the answer is the maximum value present in the DP table, since any valid distribution of items across both bags could correspond to any state.

Why it works

This algorithm works because it systematically explores all valid subsets of items while respecting capacity constraints, and it ensures optimal substructure by building solutions for larger item sets from previously computed smaller subsets. The reverse iteration guarantees that each item is considered exactly once per state transition, preserving correctness of the knapsack formulation.

Python Solution

from typing import List

class Solution:
    def maxWeight(self, weights: List[int], w1: int, w2: int) -> int:
        dp = [[0] * (w2 + 1) for _ in range(w1 + 1)]
        
        for w in weights:
            for i in range(w1, -1, -1):
                for j in range(w2, -1, -1):
                    best = dp[i][j]
                    
                    if i >= w:
                        best = max(best, dp[i - w][j] + w)
                    
                    if j >= w:
                        best = max(best, dp[i][j - w] + w)
                    
                    dp[i][j] = best
        
        return max(max(row) for row in dp)

The implementation builds a 2D DP table where each entry represents the best achievable total weight for given remaining capacities of the two bags. For each item, we update the table in reverse order to ensure we do not reuse the same item multiple times in a single iteration. The transitions explicitly consider placing the item in either bag or skipping it, ensuring all valid configurations are explored.

Go Solution

func maxWeight(weights []int, w1 int, w2 int) int {
	dp := make([][]int, w1+1)
	for i := range dp {
		dp[i] = make([]int, w2+1)
	}

	for _, w := range weights {
		for i := w1; i >= 0; i-- {
			for j := w2; j >= 0; j-- {
				best := dp[i][j]

				if i >= w {
					if dp[i-w][j]+w > best {
						best = dp[i-w][j] + w
					}
				}

				if j >= w {
					if dp[i][j-w]+w > best {
						best = dp[i][j-w] + w
					}
				}

				dp[i][j] = best
			}
		}
	}

	ans := 0
	for i := 0; i <= w1; i++ {
		for j := 0; j <= w2; j++ {
			if dp[i][j] > ans {
				ans = dp[i][j]
			}
		}
	}

	return ans
}

The Go implementation mirrors the Python logic using slices for the 2D DP table. Since Go does not have built-in max functions for integers, comparisons are done explicitly. The structure of the algorithm remains identical, including reverse iteration to ensure correctness of state transitions.

Worked Examples

Example 1

Input: weights = [1,4,3,2], w1 = 5, w2 = 4

We begin with a DP table initialized to zero. We process items one by one.

After processing weight 1, we can place it in either bag, so dp reflects states where either bag has capacity used as 1.

After processing weight 4, we can place it in bag 2 or bag 1 depending on remaining capacity.

After processing weight 3 and 2, the best configuration becomes placing 3 and 2 into bag 1 (total 5), and placing 4 into bag 2.

Final DP maximum value is 9.

Example 2

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

Processing 8 first allows it to go into bag 1. Then 3 and 4 combine into bag 2, reaching 7. The 6 cannot improve the optimal configuration without violating constraints.

Final DP maximum value is 15.

Example 3

Input: weights = [5,7], w1 = 2, w2 = 3

Neither item fits into either bag. DP remains zero throughout all transitions, so result is 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n · w1 · w2) Each item updates a full 2D DP grid
Space O(w1 · w2) DP table storing best values for each capacity pair

The complexity arises because for each item we iterate through every possible capacity combination of both bags. This is necessary because each item influences both dimensions independently.

Test Cases

assert Solution().maxWeight([1,4,3,2], 5, 4) == 9  # standard optimal split
assert Solution().maxWeight([3,6,4,8], 9, 7) == 15  # mixed distribution
assert Solution().maxWeight([5,7], 2, 3) == 0  # no item fits
assert Solution().maxWeight([1], 1, 1) == 1  # single item fits either bag
assert Solution().maxWeight([2,2,2], 4, 2) == 4  # split across bags
assert Solution().maxWeight([10,1,1], 10, 1) == 11  # heavy item + small item
assert Solution().maxWeight([3,3,3], 3, 3) == 6  # balanced packing
Test Why
[1,4,3,2], 5, 4 verifies optimal split across both bags
[3,6,4,8], 9, 7 tests interaction between large and medium items
[5,7], 2, 3 verifies all items rejected case
[1], 1, 1 single element assignment correctness
[2,2,2], 4, 2 checks distribution across constrained capacities
[10,1,1], 10, 1 ensures greedy failure avoidance
[3,3,3], 3, 3 symmetry and balanced packing

Edge Cases

One important edge case occurs when no items fit into either bag. In this situation, the DP table remains at its initialized zero values, and the algorithm correctly returns zero without any special handling.

Another edge case is when all items individually fit into only one of the bags but not both combined in an optimal way. The DP formulation correctly handles this because it explicitly considers both placement choices for each item, allowing redistribution between bags rather than forcing greedy assignment.

A further edge case arises when item sizes are large relative to capacities, especially when only one item can fit into a bag. The reverse iteration ensures that we do not reuse items and that each item is considered exactly once per state transition, preserving correctness even in tightly constrained scenarios.