动态规划·dp·01背包

NEKO_Daze · 2023-08-31 15:02:52 · 个人记录

本帖部分内容取自OI wiki，若有侵权立即删除，特此声明

01 背包

1. 引入

考虑下面这种问题

已知有 n 件物品，第 i 件物品的大小为 w_i ， 价值为 v_i ， 还有一个容量为 W 的背包。在不超过背包容量大小的情况下往背包里装物品，求能得到的总最大价值。

这就是典型的01 背包问题

2.思考过程

01 背包是典型的背包问题，而大多背包问题可以用动态规划（DP）解决。

设一个存储DP状态的数组 f ， f_{i, j} 表示在只能放前 i 个物品的情况下，容量为 j 的背包所能达到的最大总价值。

接下来考虑状态转移方程。

假设当前已经处理好了前 i-1 个物品的所有状态，那么对于第 i 个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 f_{i-1,j} ；

当其放入背包时，背包的剩余容量会减小 w_{i} ，背包中物品的总价值会增大 v_{i} ，故这种情况的最大价值为 f_{i-1,j-w_{i}}+v_{i} 。

由此，可以得出状态转移方程为

请记住该方程式，这个式子很重要。

3.代码实现

我们使用双层嵌套循环来枚举每个状态 f_{i ,j} ，外层循环枚举 i ， 内层循环枚举 j 。

for (int i = 1; i <= n; i++)
{
    for (int j = w[i]; j <= W; j++)
    {

    }
}

事实上，这正是完全背包问题的解法

然后请出我们的状态转移方程，就得到了01 背包的核心代码。

//核心代码
for (int i = 1; i <= n; i++)
{
    for (int j = w[i]; j <= W; j++) 
    {
        f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
    }
}

由此，我们就能解决开头所提出的问题了。

#include <bits/stdc++.h> //万能头文件
using namespace std;
int n, v[105], w[105], W, f[105][105];
int main()
{
    cin >> n >> W; //读入数据
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i] >> v[i]; //读入大小与价值
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = w[i]; j <= W; j++) 
        {
            f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]); //状态转移方程
        }
    }
    cout << f[n][W];
    return 0;
}

4.优化代码

刚才我们使用的是二维数组，容易MLE。能不能优化一下空间呢？能。

我们可以用一维数组，这样空间能减少一半。

运用滚动数组的思路，我们可以继续思考：

由于对 f_i 有影响的只有 f_{i-1} ，可以去掉第一维，直接用 f_{i} 来表示处理到当前物品时背包容量为 i 的最大价值，得出以下方程：

这其中，f_j 的含义是不断变化的。

然后，我们改一下我们的核心代码：

for (int i = 1; i <= n; i++)
{
    for (int j = W; j >= w[i]; j--) //倒序枚举！！！很重要！！！
    {
    f[j] = max(f[j], f[j - w[i]] + v[i]);
    }
}

为什么内层循环要倒序枚举呢？

对于当前处理的物品 i 和当前状态 f_{i,j} ，在 j\ge w_{i} 时，f_{i,j} 是会被 f_{i,j-w_{i}} 所影响的。这就相当于物品 i 可以多次被放入背包，与题意不符。

这样，我们就可以优化刚才的代码了：

#include <bits/stdc++.h> 
using namespace std;
int n, v[105], w[105], W, f[105];
int main()
{
    cin >> n >> W;
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = W; j >= w[i]; j--) 
        {
            f[j] = max(f[j], f[j - w[i]] + v[i]);
        }
    }
    cout << f[W];
    return 0;
}