LeetCode 第41天 | 背包问题 二维数组 一维数组 416.分割等和子集 动态规划

46. 携带研究材料（第六期模拟笔试）
题目描述
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

输入描述
第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。

第三行包含 M 个正整数，代表每种研究材料的价值。

输出描述
输出一个整数，代表小明能够携带的研究材料的最大价值。
输入示例
6 1
2 2 3 1 5 2
2 3 1 5 4 3
输出示例
5
提示信息
小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。

数据范围：
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空间和价值都小于等于 1000

思路：纯正的01背包问题
二维数组方法：dp[i][j]中i表示第几个物品，j表示容量[0, n]，当背包容量大于当前物品权重时，递推公式为:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])，即从左上方推出；
容量小于当前物品权重时直接从上方赋值，即dp[i][j] = dp[i-1][j]。初始化时第一列表示容量为0的最大价值，初始化为0，第一行中如果当前容量大于等于第1个物品的权重value[0]时，初始化为value[0]，否则为value[1]。
这样就可以从左上方来推啦。

#include<iostream>
#include<vector>
#include <bits/stdc++.h>
using namespace std;
int solve(int M, int N) {
    vector<int> weight(M,0);
    vector<int> value(M,0);
    for (int i = 0; i<M; i++) {
        cin>>weight[i];
    }
    for (int i = 0; i<M; i++) {
        cin>>value[i];
    }
    vector<vector<int>> dp(M, vector<int>(N+1, 0));
    for (int j = weight[0]; j<=N; j++) {
        dp[0][j] = value[0];
    }
    for (int i = 1; i<M; i++) {
        for (int j = 0; j<=N; j++) {
            if (j < weight[i])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
        }
    }
    cout<<dp[M-1][N];
}
int main() {
    int M,N;
    while(cin>>M>>N){
        solve(M,N);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

一维dp思路：二维数组压缩成一维数组，即滚动数组，可以节省空间。因为观察递推公式：dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])，可以看到，本行的递推所需数据均在上一行，且均在左侧，因此可以把上一行的数据复制到本行接着使用。因此定义一个dp[n+1]的数组即可保存完毕。dp[j]表示容量为j的最大价值，递推公式类似二维：
dp[j] = max(dp[j], dp[j-weight[i]]+value[i])。可以看到如果其实本质思想还是二维数组，但是巧妙地运用方法使二维数组变为一维数组，节省空间，代码简洁。注意遍历顺序，在二维数组中可以先物品，在容量，亦可以反过来；但是一维由于压缩，只可以先物品，后容量，容量遍历顺序必须从后向前，否则会造成数据覆盖，某些物品权重多加。

// 一维dp数组实现
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 读取 M 和 N
    int M, N;
    cin >> M >> N;

    vector<int> costs(M);
    vector<int> values(M);

    for (int i = 0; i < M; i++) {
        cin >> costs[i];
    }
    for (int j = 0; j < M; j++) {
        cin >> values[j];
    }

    // 创建一个动态规划数组dp，初始值为0
    vector<int> dp(N + 1, 0);

    // 外层循环遍历每个类型的研究材料
    for (int i = 0; i < M; ++i) {
        // 内层循环从 N 空间逐渐减少到当前研究材料所占空间
        for (int j = N; j >= costs[i]; --j) {
            // 考虑当前研究材料选择和不选择的情况，选择最大值
            dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
        }
    }

    // 输出dp[N]，即在给定 N 行李空间可以携带的研究材料最大价值
    cout << dp[N] << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100
思路：这个题就是寻找两个集合，使其子集的和相等，即各为数组总和的一半。如果使用回溯，就会是指数级的时间复杂度，因此需要用背包问题来看待。物品价值和权重的值相等，总容量为target = sum/2。递推公式为：
dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])；其余循环遍历顺序等和简单01背包相同。最后只需要返回是否可以满足条件，就是判断dp[target] == target的bool值。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        // 计算数组总价值量
        for (auto num : nums) {
            sum += num;
        }
        // 如果价值量为奇数，不可以平均分成两份，因此必为false
        if (sum % 2 == 1)   return false;
        int target = sum / 2;
        // 初始化dp数组为全0
        vector<int> dp(target + 1, 0);
        // 虽然是一维数组做dp但是还是要两层循环，外层表示物品个数，内层表示容量
        for (int i = 0; i<nums.size(); i++) {
            for (int j = target; j >= nums[i]; j--) {
                // 物品的价值和权重时一样的。均为1
                dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]);
            }
        }
        // 如果容量等于dp最后得到的状态值，返回真
        if (target == dp[target]) {
            return true;
        }
        else {
            return false;
        }

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30