Skip to content

3647. Maximum Weight in Two Bags πŸ”’

Description

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

Solutions

Solution 1: Dynamic Programming

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 \text{ 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 \(\textit{weights}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maxWeight(self, weights: List[int], w1: int, w2: int) -> int:
        f = [[0] * (w2 + 1) for _ in range(w1 + 1)]
        max = lambda a, b: a if a > b else b
        for x in weights:
            for j in range(w1, -1, -1):
                for k in range(w2, -1, -1):
                    if x <= j:
                        f[j][k] = max(f[j][k], f[j - x][k] + x)
                    if x <= k:
                        f[j][k] = max(f[j][k], f[j][k - x] + x)
        return f[w1][w2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxWeight(int[] weights, int w1, int w2) {
        int[][] f = new int[w1 + 1][w2 + 1];
        for (int x : weights) {
            for (int j = w1; j >= 0; --j) {
                for (int k = w2; k >= 0; --k) {
                    if (x <= j) {
                        f[j][k] = Math.max(f[j][k], f[j - x][k] + x);
                    }
                    if (x <= k) {
                        f[j][k] = Math.max(f[j][k], f[j][k - x] + x);
                    }
                }
            }
        }
        return f[w1][w2];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxWeight(vector<int>& weights, int w1, int w2) {
        vector<vector<int>> f(w1 + 1, vector<int>(w2 + 1));
        for (int x : weights) {
            for (int j = w1; j >= 0; --j) {
                for (int k = w2; k >= 0; --k) {
                    if (x <= j) {
                        f[j][k] = max(f[j][k], f[j - x][k] + x);
                    }
                    if (x <= k) {
                        f[j][k] = max(f[j][k], f[j][k - x] + x);
                    }
                }
            }
        }
        return f[w1][w2];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func maxWeight(weights []int, w1 int, w2 int) int {
    f := make([][]int, w1+1)
    for i := range f {
        f[i] = make([]int, w2+1)
    }
    for _, x := range weights {
        for j := w1; j >= 0; j-- {
            for k := w2; k >= 0; k-- {
                if x <= j {
                    f[j][k] = max(f[j][k], f[j-x][k]+x)
                }
                if x <= k {
                    f[j][k] = max(f[j][k], f[j][k-x]+x)
                }
            }
        }
    }
    return f[w1][w2]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function maxWeight(weights: number[], w1: number, w2: number): number {
    const f: number[][] = Array.from({ length: w1 + 1 }, () => Array(w2 + 1).fill(0));
    for (const x of weights) {
        for (let j = w1; j >= 0; j--) {
            for (let k = w2; k >= 0; k--) {
                if (x <= j) {
                    f[j][k] = Math.max(f[j][k], f[j - x][k] + x);
                }
                if (x <= k) {
                    f[j][k] = Math.max(f[j][k], f[j][k - x] + x);
                }
            }
        }
    }
    return f[w1][w2];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
impl Solution {
    pub fn max_weight(weights: Vec<i32>, w1: i32, w2: i32) -> i32 {
        let w1 = w1 as usize;
        let w2 = w2 as usize;
        let mut f = vec![vec![0; w2 + 1]; w1 + 1];
        for &x in &weights {
            let x = x as usize;
            for j in (0..=w1).rev() {
                for k in (0..=w2).rev() {
                    if x <= j {
                        f[j][k] = f[j][k].max(f[j - x][k] + x as i32);
                    }
                    if x <= k {
                        f[j][k] = f[j][k].max(f[j][k - x] + x as i32);
                    }
                }
            }
        }
        f[w1][w2]
    }
}

Comments