动态规划04-用滚动数组降维解决01背包问题

问题描述

有一个容量为V的背包，还有n个物体。现在忽略物体实际几何形状，我们认为只要背包的剩余容量大于等于物体体积，那就可以装进背包里。每个物体都有两个属性，即体积w和价值v。
问：如何向背包装物体才能使背包中物体的总价值最大？

思路分析

在昨天做了用二维数组解决01背包问题，今天尝试将二维数组降维成一维数组，思路来源是在之前的递推公式中当不需要添加物品i的时候，dp[i][j]的值就是dp[i-1][j]，这样一来，如果只是用一维，就能实现dp[i]=dp[i]。

1. 确定dp[j]的含义：在容量为i的背包中物品最大的价值是dp[j]。
2. 确定递推公式：dp[j]的值由dp[j-1]决定，当要添加当前物品的时候，价值是dp[j]=dp[j-weight[i]]+value[i]，如果不需要添加，那么就是dp[j]=dp[j-1]；
3. 一维数组初始化，当背包容量为0的时候，就是0，当背包是1的时候，就是value[1]。
4. 遍历顺序：按照遍历物品的顺序进行
5. 代入数据验证

代码

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