Maximum weight in two bags

Array Dynamic Programming

57.9% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_weight(weights: Vec<i32>, w1: i32, w2: i32) -> i32 {
    let w1 = w1 as usize;
    let w2 = w2 as usize;
    // dp[j1][j2] = max weight using at most j1 in bag1, j2 in bag2
    let mut dp = vec![vec![0i32; w2 + 1]; w1 + 1];

    for &w in &weights {
      let wu = w as usize;
      // Iterate backwards to avoid using same item twice
      for j1 in (0..=w1).rev() {
        for j2 in (0..=w2).rev() {
          if j1 + wu <= w1 {
            dp[j1 + wu][j2] = dp[j1 + wu][j2].max(dp[j1][j2] + w);
          }
          if j2 + wu <= w2 {
            dp[j1][j2 + wu] = dp[j1][j2 + wu].max(dp[j1][j2] + w);
          }
        }
      }
    }

    dp[w1][w2]
  }
}