JZTXT

总结： [01背包] 空间优化后内层循环为啥是逆序的?

发布时间 2023-08-05 11:01:21作者: VEX棒棒哒

总结： [01背包] 空间优化后内层循环为啥是逆序的?
首先，这是一个困扰了不少人的问题，虽然网上有挺多的解释，但是有的想起来比较费劲，于是乎，就有了这篇题解

题目分析

  • 首先，01背包问题是一个非常非常非常经典的动态规划问题(后文简称“动规”或“dp”)。
  •  因为百度百科上的题目分析比较详细 （我比较懒），所以就拿来做参考了

01背包是在N件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2至Wn，与之相对应的价值为V1,V2至Vn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。

（摘自：百度百科）

 正文
1. 首先，我们想要知道优化后的思路，就得先来看原版的↓
大体思路：以“第i件物品在背包体积为j时的最大价值”循环递推出“N件物品取若干件放在空间为W的背包里”(即dp[N][W])的最大价值。

话不多说，直接上代码↓

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int dp[110][10100];
 4 int w[110], v[110];
 5 int N, W;
 6 int main(){
 7     cin >> N >> W ;
 8     for(int i=1;i<=N;i++)cin>>w[i]>>v[i];
 9     memset(dp, 0, sizeof(dp));
10 
11    for(int i=1;i<=N;i++){
12        for(int j=1;j<=W;j++){
13            if(j < w[i]) dp[i][j] = dp[i-1][j];
14            //如果w[i]>j，第i个物品一定不能选择
15            else{
16                //否则在第i个物品选与不选中选择较大的 
17                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
18           }
19       }
20   }
21     cout<<"max="<<dp[N][W];
22     return 0;
23 }

2. 现在，我们再来看优化过的（优化空间）
那么，我们为什么可以优化呢？
我们发现，每一行的数据都只与上一行有关，所以就可以把二维的dp数组变成一维的“滚动数组”。
只看文字可能不太好理解，于是贴心的我就画了个表↓

 

  0 1 2 3
0 y      
1 x      
2        
3        

（行为i，列为j）结合上面的代码不难看出， x格的值只与

dp[i-1][j]或dp[i-1][j-w[i]]+v[i]

即y格或与y格前面同一行的其他格有关（划重点）

所以，当dp数组变为一维时，x格前面同一行的其他格都已经把原本y那一行的覆盖掉了，而x格从前面取的数值就可能会是更新过的，造成答案错误。

其他格同理，而倒序则不会覆盖掉前面的，所以里层循环（即j的循环）要是倒序的。

道理都讲完了，为了防止有人还是懵的，这里附上一篇用数据验证的文章↓
https://blog.csdn.net/xiajiawei0206/article/details/19933781

 顺带说一句，如果优化空间后的里层循环是正着的，那么表示一个物品被重复取了，

所以，完全背包问题刚好可以用这种解法。

 写在最后

最后，附上优化过的代码↓

对不起，2023年3月27日19:42:23复习DP的时候才发现放成完全背包的了。以下是正确代码↓

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     int n;
 5     cin >> n;
 6     int ww[n+4], v[n+4];
 7     for(int i=1;i<=n;i++)   cin >> ww[i] >> v[i];
 8     int W;
 9     cin >> W;
10     int dp[W+4];
11     memset(dp, 0, sizeof(dp));
12     for(int i=1;i<=n;i++){
13         for(int j=W;j>=1;j--){
14             if(j >= ww[i]){
15                 dp[j] = max(dp[j], dp[j-ww[i]]+v[i]);
16             }
17         }
18     }
19     cout << dp[W];
20     return 0;
21 }

完全背包

  •   既然写错了，那就将错就错，讲下完全背包吧

（先放个代码，下次在写）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int dp[204];
 4 int w[32], v[32];
 5 int N, W;
 6 int main(){
 7     cin>>W>>N;
 8     for(int i=1;i<=N;i++)cin>>w[i]>>v[i];
 9     memset(dp, 0, sizeof(dp));
10     for(int i=1;i<=N;i++){
11         for(int j=w[i];j<=W;j++){
12             dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
13         }
14     }
15     cout<<"max="<<dp[W];
16     return 0;
17 }

感谢 提供参考：https://blog.csdn.net/xiajiawei0206/article/details/19933781