AcWing 2. 01背包问题为何优化为一维为何逆序

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 2. 01背包问题为何优化为一维为何逆序原题链接简单

作者：

断然 , 2022-05-16 21:53:41 , 所有人可见 , 阅读 6848

209

152

为什么可以转为一维

首先观察状态转移方程 dp[i][j]是由 dp[i-1][jxxxx]推导而来，仅看第一个维度，即i - 1 与 i ，可以发现第i层是由上一层推导而来的。

故我们不必要保存i - 2 层，比如我们计算第三层是只需要第二层的。不需要第一层的数据。

当我们去掉i时，即我们不需要控制第几层，只需要长度为j的数组，保存确认过最新的一层。作为下一层的参考。例如我们计算第三层dp时，此时dp原数据保存的是第二层的结果。

为什么要逆序

首先，通过上一个问题，我们确认了我们目前一维的dp数组，保存的是确认过的最新一层的数据，即上一层的数据。

当我们计算当前层时，对于二维时的状态转移方程有

dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);

可以看到，dp[i - 1][j - v[i]] + w[i] 使用的上一层的原始数据（dp[i - 1]），而我们使用一维的状态转移方程时有

dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

当我们从小到大更新是，因为j - v[i] 是严格小于j 的，所以我们可以举个例子 dp[3] = max(dp[3], dp[2] + 1); 因为我们是从小到大更新的，所以当更新到dp[3]的时候，dp[2]已经更新过了，已经不是上一层的dp[2]。

而当我们逆序更新时有，举例 dp[8] = max(dp[8], dp[6] + 2)当更新dp[8]时，dp[6]还没有被更新，还是上一层的数据，这样才能保证没有读入脏数据。

二维代码如下

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int n, m;
int dp[N][N];
int v[N], w[N];

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }

    cout << dp[n][m];
    return 0;
}

一维dp代码如下

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int n, m;
int dp[N];
int v[N], w[N];

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j --)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << dp[m];
    return 0;
}

52 评论

这道题不过如此 2022-06-30 21:03

这个才是大佬，感觉这个题解思路很好，非常容易懂，其他人的太乱太抽象了，强烈推荐！！！

不对 2023-02-07 19:51

同感，一眼看懂了

不摘月 2024-02-05 12:56

同感同感

Vivi000 2024-03-27 17:20

同感同感

摆神 2024-03-18 19:21

为什么需要逆序：

因为：此时f[j-v[i]] ≠ 二维数组f[i-1][j-v[i]]+w[i]:
解释：通过第二个for顺序循环j按顺序从0->m的话dp[j] = 二维数组的f[i][j - v[i]]+w[i]，【比如dp[3] = max(dp[3], dp[2] + 1);因为正序j从0->m ,dp[j]是从小到大更新，j=3中dp[2]已经更新成的前i个物品dp[2],但此时我们要求的是前i-1个物品下的dp[2]】，所以只有逆序第二个for的j进行循环时f[j-v[i]]，dp[j]从大到小更新，较小的数还是二维数组的f[i-1][j-v[i]]+w[i]。【比如dp[8] = max(dp[8], dp[6] + 2)当更新dp[8]时，在这第二个for循环中dp[6]还没有被更新，还是第一个for循环中前i-1个物品的dp[6]】.这样才不是被污染的数据。

yuxiaojia 2024-03-20 01:16

谢谢，懂了！

XinyeChu 2023-03-29 15:49

n=4 m=5//物品个数为4，背包总体积为5

v[1]=1,w[1]=5;
v[2]=2,w[2]=4
v[3]=3,w[3]=4
v[4]=4,w[4]=5

for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]);

01背包,逆序排列
//依次判断每个物品
//初始化全局定义f[N]=0
i=1 j=5 此时j>=v[1]  f[5]=max(f[5],f[5-v[1]]+w[1])=max(f[5],f[4]+5)=5;//1
i=1 j=4 此时j>=v[1]  f[4]=max(f[4],f[4-v[1]]+w[1])=max(f[4],f[3]+5)=5;//1
i=1 j=3 此时j>=v[1]  f[3]=max(f[3],f[3-v[1]]+w[1])=max(f[3],f[2]+5)=5;//1
i=1 j=2 此时j>=v[1]  f[2]=max(f[2],f[2-v[1]]+w[1])=max(f[2],f[1]+5)=5;//1
i=1 j=1 此时j>=v[1]  f[1]=max(f[1],f[1-v[1]]+w[1])=max(f[1],5)=5;//1

i=2,j=5 此时j>=v[2]  f[5]=max(f[5],f[5-v[2]]+v[2])=max(f[5],f[3]+4)=max(5,5+4)=9 //1 2
i=2,j=4 此时j>=v[2]  f[4]=max(f[4],f[4-v[2]]+v[2])=max(f[4],f[2]+4)=max(5,5+4)=9 //1 2
i=2,j=3 此时j>=v[2]  f[3]=max(f[3],f[3-v[2]]+v[2])=max(f[3],f[1]+4)=max(5,5+4)=9 //1 2
i=2,j=2 此时j>=v[2]  f[2]=max(f[2],f[2-v[2]]+v[2])=max(f[2],f[0]+4)=max(5,4)=5 // 1

i=3,j=5 此时j>=v[3] f[5]=max(f[5],f[5-v[3]]+v[3])=max(f[5],f[2]+4)=max(9,5+4)=9 //1+2 1+3
i=3,j=4 此时j>=v[3] f[4]=max(f[4],f[4-v[3]]+v[3])=max(f[4],f[1]+4)=max(9,5+4)=9 //1+2 1+3
i=3,j=3 此时j>=v[3] f[3]=max(f[3],f[3-v[3]]+v[3])=max(f[3],f[0]+4)=max(9,4)=9 //1+2
………//后续省略

完全背包，正序排列

n=4 m=5//物品个数为4，背包总体积为5
v[1]=1,w[1]=5;
v[2]=2,w[2]=4
v[3]=3,w[3]=4
v[4]=4,w[4]=5

for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

//判断第一个物体
i=1 j=1 此时j<m f[1]=max(f[1],f[j-v[1]]+w[1])=max(f[1],f[1-1]+5)=max(0,5)=5//1//一个1
i=1 j=2 此时j<m f[2]=max(f[2],f[j-v[1]]+w[1])=max(f[2],f[2-1]+5)=max(0,5+5)=10//两个1
i=1 j=3 此时j<m f[3]=max(f[3],f[j-v[1]]+w[1])=max(f[3],f[3-1]+5)=max(0,10+5)=15//三个1
i=1 j=4 此时j<m f[4]=max(f[4],f[j-v[1]]+w[1])=max(f[4],f[4-1]+5)=max(0,15+5)=20//四个1
i=1 j=5 此时j=m f[5]=max(f[5],f[j-v[1]]+w[1])=max(f[5],f[5-1]+5)=max(0,20+5)=25//五个1

i=2 j=2 此时j<m f[2]=max(f[2],f[j-v[2]]+w[2]=max(f[2],f[2-1]+4)=max(10,5+4)=10//两个1
i=2 j=3 此时j<m f[3]=max(f[3],f[j-v[2]]+w[2]=max(f[3],f[3-1]+4)=max(15,10+4)=15//三个1
i=2 j=4 此时j<m f[4]=max(f[4],f[j-v[2]]+w[2]=max(f[4],f[4-1]+4)=max(20,15+4)=20//四个1
i=2 j=5 此时j<m f[5]=max(f[5],f[j-v[2]]+w[2]=max(f[5],f[5-1]+4)=max(25,20+4)=25//五个1
………//后续省略