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

Thinking

Each item may go into a bag of capacity \(w_1\), a bag of capacity \(w_2\), or neither. That is a two-dimensional \(0\)-\(1\) knapsack. \(n\le 100\) and \(w\le 300\) allow a compressed \(f[j][k]\).

\(f[j][k]\) is the best total when the residual capacities are \(j\) and \(k\). Capacities are scanned backwards so an item is used at most once.

For weight \(x\), try \(f[j-x][k]+x\) and \(f[j][k-x]+x\). The answer is \(f[w_1][w_2]\).

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}\).

Python3JavaC++GoTypeScriptRust

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]

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];
    }
}

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];
    }
};

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]
}

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];
}

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]
    }
}

3647. Maximum Weight in Two Bags 🔒

Description

Solutions

Solution 1: Dynamic Programming

Comments