每日OJ题_01背包①_牛客DP41 【模板】01背包（滚动数组优化）

目录

牛客DP41 【模板】01背包

问题一解析

问题二解析

解析代码

滚动数组优化代码

牛客DP41 【模板】01背包

【模板】01背包_牛客题霸_牛客网

#include <iostream>
using namespace std;

int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        cout << a + b << endl;
    }
}
// 64 位输出请用 printf("%lld")

问题一解析

背包问题的状态表示非常经典，如果不知道怎么来的，可以先把它当成一个模板。

以某个位置为结尾，结合题目要求，定义一个状态表示：

dp[i][j] 表示：从前 i 个物品中挑选，总体积不超过 j ，所有的选法中，能挑选出来的最大价值。

状态转移方程：

线性 dp 状态转移方程分析方式，一般都是根据最后一步的状况，来分情况讨论：

• 不选第 i 个物品：相当于就是去前 i - 1 个物品中挑选，并且总体积不超过 j 。此时 dp[i][j] = dp[i - 1][j] ;。
• 选择第 i 个物品：那么就只能去前 i - 1 个物品中，挑选总体积不超过 j - v[i] 的物品。此时 dp[i][j] = dp[i - 1][j - v[i]] + w[i] ; 。但是这种状态不一定存在，要判断 j >= v[i]。

综上，状态转移方程为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) ;

初始化、填表顺序、返回值：

        多加一行，方便初始化，此时仅需将第一行初始化为 0 即可。因为什么也不选，也能满足体积不小于 j 的情况，此时的价值为 0 。填表顺序从左往右，最后返回dp[n][V] ; 

问题二解析

        第二问仅需微调一下 dp 过程的五步即可。 因为有可能凑不齐 j 体积的物品，因此把不合法的状态设置为 -1 。

以某个位置为结尾，结合题目要求，定义一个状态表示：

dp[i][j] 表示：从前 i 个物品中挑选，总体积正好等于 j ，所有的选法中，能挑选出来的最大价值。

状态转移方程：

线性 dp 状态转移方程分析方式，一般都是根据最后一步的状况，来分情况讨论：

• 不选第 i 个物品：相当于就是去前 i - 1 个物品中挑选，并且总体积不超过 j 。此时 dp[i][j] = dp[i - 1][j] ;。
• 选择第 i 个物品：那么就只能去前 i - 1 个物品中，挑选总体积不超过 j - v[i] 的物品。此时 dp[i][j] = dp[i - 1][j - v[i]] + w[i] ; 。但是这种状态不一定存在，不仅要判断 j >= v[i] ，还要判断 dp[i - 1][j - v[i]] 表示的情况是否存在，也就是 dp[i - 1][j - v[i]] != -1 。

综上，状态转移方程为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) ;

初始化、填表顺序、返回值：

        多加一行，方便初始化，第一行第一个格子为 0 ，因为正好能凑齐体积为 0 的背包，但是第一行第一个格子后面都是 -1 ，因为没有物品，无法满足体积大于 0 的情况。第一列全为0。

填表顺序从左往右，最后返回dp[n][V] ; 

解析代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010; // OJ定义成全局方便，且空间不会轻易溢出
int n, V, v[N], w[N];
int dp[N][N];

int main()
{
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) // 从1开始读数据
    {
        cin >> v[i] >> w[i];
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j <= V; ++j)
        {
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i])
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << dp[n][V] << endl;

    memset(dp, 0, sizeof(dp));
    for(int j = 1; j <= V; ++j)
    {
        dp[0][j] = -1;
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j <= V; ++j)
        {
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i] && dp[i - 1][j - v[i]] != -1)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;

    return 0;
}

滚动数组优化代码

背包问题基本上都是利用滚动数组来做空间上的优化：（时间也有常数的优化）

1. 利用滚动数组优化。
2. 直接在原始代码上修改。

        第i行元素只依赖于第i-1行元素。理论上，只需要保持两行元素，所以只需两个数组交替滚动，就能完成dp数组的填充。因此空间复杂度从O（N^2） 变为O（N）。

        这里还可以直接用一个数组来进行优化：从前往后去更新数组，dp[j - v[ i ]]肯定不比dp[ j ]的值大，而改了前面，后面的更新就会用到前面更新的数据，而本来应该使用原二维数组 i - 1行的数据，也就是更新数据之前的，因此可以巧妙地从后往前遍历，这样就可以避免用到更新后的数据。

在01背包问题中，优化的结果为：

1. 删掉所有的横坐标。
2. 修改一下 j 的遍历顺序。

（滚动数组优化代码只需能在原代码上修改就行，不用考虑什么状态表示）

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010; // OJ定义成全局方便，且空间不会轻易溢出
int n, V, v[N], w[N];
// int dp[N][N];
int dp[N]; // 滚动数组优化，把所有dp表左边一维坐标删掉，修改遍历顺序

int main()
{
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) // 从1开始读数据
    {
        cin >> v[i] >> w[i];
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = V; j >= v[i]; --j) // 滚动数组优化
        {
            dp[j] = dp[j];
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[V] << endl;

    memset(dp, 0, sizeof(dp));
    for(int j = 1; j <= V; ++j)
    {
        dp[j] = -1;
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = V; j >= v[i]; --j) // 滚动数组优化
        {
            if(dp[j - v[i]] != -1)
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;

    return 0;
}