跳转至

3647. 两个袋子中的最大重量 🔒

题目描述

给定一个整数数组 weights 和两个整数 w1 和 w2 表示两个袋子的 最大 容量。

每个物品 最多 可以放入一个袋子中，使得：

  • 袋子 1 最多 总共可以装 w1 重量。
  • 袋子 2 最多 总共可以装 w2 重量。

返回两个袋子可以装入的 最大 总重量。

 

示例 1：

输入：weights = [1,4,3,2], w1 = 5, w2 = 4

输出：9

解释：

  • 袋子 1：放入 weights[2] = 3 和 weights[3] = 2 满足 3 + 2 = 5 <= w1
  • 袋子 2：放入 weights[1] = 4 满足 4 <= w2
  • 总重量：5 + 4 = 9

示例 2：

输入：weights = [3,6,4,8], w1 = 9, w2 = 7

输出：15

解释：

  • 袋子 1：放入 weights[3] = 8 满足 8 <= w1
  • 袋子 2：放入 weights[0] = 3 和 weights[2] = 4 满足 3 + 4 = 7 <= w2
  • 总重量：8 + 7 = 15

示例 3：

输入：weights = [5,7], w1 = 2, w2 = 3

输出：0

解释：

没有可以放入两个袋子中的重量，所以答案为 0。

 

提示：

  • 1 <= weights.length <= 100
  • 1 <= weights[i] <= 100
  • 1 <= w1, w2 <= 300

解法

方法一：动态规划

我们定义 \(f[i][j][k]\) 表示前 \(i\) 个物品放入两个袋子中，袋子 1 的最大容量为 \(j\)，袋子 2 的最大容量为 \(k\) 时的最大总重量。初始时 \(f[0][j][k] = 0\)，表示没有物品可放入袋子中。

状态转移方程为：

\[ 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) \]

其中 \(w_i\) 表示第 \(i\) 个物品的重量。

最终答案为 \(f[n][w1][w2]\)，其中 \(n\) 为物品数量。

我们注意到状态转移方程中只依赖于前一层的状态，因此可以将三维 DP 数组压缩为二维 DP 数组。在枚举 \(j\) 和 \(k\) 时，我们采用倒序遍历的方式。

时间复杂度 \(O(n \times w1 \times w2)\)，空间复杂度 \(O(w1 \times w2)\)。其中 \(n\) 是数组 \(\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]
    }
}

评论