蓝桥杯备考：01背包之优化问题。

在谈背包的优化的时间，我们先回首一下之前的数字三角形问题，我们先用这道题举行一下优化，在谈我们01背包的优化

step1：分析状态表示 f[j]表示i，j这个格子的最大路径和
step2；分析状态转移方程

填每个格子都必要正上方和左上方的最大路径加该点的权值取最大
so f[j] = max(f[i-1][j],f[i-1][j-1]) + a[j]
step3 初始化

由于啊我们每个点的权值都是正整数大概0，
以是刚开始的时间我们只要把数组全部初始化为0就行了

1. #include <iostream>
2. using namespace std;
3. const int N = 1010;
4. int n;
5. int a[N][N];
6. int f[N][N];
7. int main()
8. {
9.         cin >> n;
10.         for(int i = 1;i<=n;i++)
11.         {
12.                 for(int j = 1;j<=i;j++)
13.                 {
14.                         cin >> a[i][j];
15.                 }
16.         }
17.        
18.         for(int i = 1;i<=n;i++)
19.         {
20.                 for(int j = 1;j<=i;j++)
21.                 {
22.                         f[i][j] = max(f[i-1][j],f[i-1][j-1])+a[i][j];       
23.                 }
24.         }
25.         int ret = 0;
26.         for(int i = 1;i<=n;i++)
27.         {
28.                 ret = max(ret,f[n][i]);
29.         }
30.         cout << ret << endl;
31.        
32.        
33.         return 0;
34. }

复制代码

接下来我们就来做一下空间优化，怎样把二维转换成一维
我们的第一想法一定是开两个数组，第一个数组是填完的数组，第二个数组根据第一个数组从左往右依次填，

其实还能进一步的优化，我们只必要开一个数组，

每个位置应该填成它当前的值+上一个值，但是我们从左往右填的话就会导致填第二个的时间，第一个值已经变成新的了，我们无法包管其正确性，so我们正确的做法就应该是反着填
now 我们修改一下我们的代码
非常简单，我们只必要做两个事情，1.删除dp数组的一维 2.看看需不必要修改遍历顺序，即可

1. #include <iostream>
2. using namespace std;
3. const int N = 1010;
4. int n;
5. int a[N][N];
6. int f[N];
7. int main()
8. {
9.         cin >> n;
10.         for(int i = 1;i<=n;i++)
11.         {
12.                 for(int j = 1;j<=i;j++)
13.                 {
14.                         cin >> a[i][j];
15.                 }
16.         }
17.        
18.         for(int i = 1;i<=n;i++)
19.         {
20.                 for(int j = i;j>=1;j--)
21.                 {
22.                         f[j] = max(f[j],f[j-1])+a[i][j];       
23.                 }
24.         }
25.         int ret = 0;
26.         for(int i = 1;i<=n;i++)
27.         {
28.                 ret = max(ret,f[i]);
29.         }
30.         cout << ret << endl;
31.        
32.        
33.         return 0;
34. }

复制代码

这就是我们的空间优化，但是对这道题来说，收益其实是不大的，因为我们的空间应该是富足的，but 对背包问题来说，假如我们对背包问题举行了空间优化，它的时间也是同样会被优化的
我们来重新回首一下我们的01背包问题

先做第一小问：step1:定义状态表示f[j]表示从1到i里选出体积不超过j的最大价值
step2:确定状态转移方程

选和不选的结果取最大值
当然了，我们要选某一个格子的话一定要确定这个格子本身体积是不超过v[j]的
step3:初始化
直接填表，0是不影响结果的，

step4:结果，结果就存在f[n][m]里

1. #include <iostream>
2. using namespace std;
3. const int N  = 1010;
4. int n,m;
5. int v[N],w[N];
6. int f[N][N];
7. int main()
8. {
9.         cin >> n >> m;
10.         for(int i = 1;i<=n;i++)
11.         {
12.                 cin >> v[i] >> w[i];
13.         }
14.        
15.         for(int i = 1;i<=n;i++)
16.         {
17.                 for(int j=1;j<=m;j++)
18.                 {
19.                         f[i][j] = f[i-1][j];
20.                         if(j>=v[i])
21.                         {
22.                                 f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
23.                         }
24.                 }
25.         }
26.        
27. cout << f[n][m] << endl;
28.        
29.        
30.         return 0;
31. }

复制代码

嗯。我们举行一下空间优化，还是老样子，我们先确定一下空间优化的顺序

我们填每一个格子都是必要左边大概它本身的值，假如我们从左往右填的话，更新右边的值的时间左边的已经改完了，so遍历顺序应该还是从右往左，我们修改一下

1. #include <iostream>
2. using namespace std;
3. const int N  = 1010;
4. int n,m;
5. int v[N],w[N];
6. int f[N];
7. int main()
8. {
9.         cin >> n >> m;
10.         for(int i = 1;i<=n;i++)
11.         {
12.                 cin >> v[i] >> w[i];
13.         }
14.        
15.         for(int i = 1;i<=n;i++)
16.         {
17.                 for(int j=m;j>=v[i];j--)
18.                 {
19.                        
20.                                 f[j] = max(f[j],f[j-v[i]]+w[i]);
21.                        
22.                 }
23.         }
24.        
25.         cout << f[m] << endl;
26.                
27.        
28.         return 0;
29. }

复制代码

我们再做一下第二小问
step1:定义状态表示 f[j]表示从1到i选出恰恰等于体积j的最大价值
step2:推导状态转移方程

可以看到和第一小问的推导方程是差不多的
step3初始化，这里我们就要多留意一下了，我们不大概每个格子都能恰恰装满，一定是有无效值的，我们可以把所有格子全初始化为负无穷，然后从有效的开始填起，根据无效格子填的格子还是无效的，嗯，除此之外我们要考虑一下界限环境，最上面那层，0，0表示从0个物品选体积为0，这个格子是有效的，应该是0，我们还要考虑一下左边的界限，i从0到m，体积为0，也必要全部填0

好的，我们来实现一下代码

1. #include <iostream>
2. #include <cstring>
3. using namespace std;
4. const int N  = 1010;
5. int n,m;
6. int v[N],w[N];
7. int f[N][N];
8. int main()
9. {
10. //        cin >> n >> m;
11. //        for(int i = 1;i<=n;i++)
12. //        {
13. //                cin >> v[i] >> w[i];
14. //        }
15. //       
16. //        for(int i = 1;i<=n;i++)
17. //        {
18. //                for(int j=m;j>=v[i];j--)
19. //                {
20. //                       
21. //                                f[j] = max(f[j],f[j-v[i]]+w[i]);
22. //                       
23. //                }
24. //        }
25. //       
26. //        cout << f[m] << endl;
27.         memset(f,-0x3f,sizeof f);
28.         cin >> n >> m;
29.         for(int i =1;i<=n;i++)
30.         {
31.                 cin >> v[i] >> w[i];
32.         }       
33.         for(int i = 1;i<=n;i++)
34.         {
35.                 f[i][0] = 0;
36.         }
37.         for(int i = 1;i<=n;i++)
38.         {
39.                 for(int j =1;j<=m;j++)
40.                 {
41.                         f[i][j] = f[i-1][j];
42.                         if(j>=v[i])
43.                         {
44.                                 f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
45.                         }
46.                 }
47.         }
48.    cout << f[n][m] << endl;
49.         return 0;
50. }

复制代码

老样子，我们继承对这段代码举行空间优化，还是看遍历顺序，去掉一维

1. #include <iostream>
2. #include <cstring>
3. using namespace std;
4. const int N  = 1010;
5. int n,m;
6. int v[N],w[N];
7. int f[N];
8. int main()
9. {
10.         cin >> n >> m;
11.         for(int i = 1;i<=n;i++)
12.         {
13.                 cin >> v[i] >> w[i];
14.         }
15.        
16.         for(int i = 1;i<=n;i++)
17.         {
18.                 for(int j=m;j>=v[i];j--)
19.                 {
20.                        
21.                                 f[j] = max(f[j],f[j-v[i]]+w[i]);
22.                        
23.                 }
24.         }
25.        
26.         cout << f[m] << endl;
27.         memset(f,-0x3f,sizeof f);
28.         cin >> n >> m;
29.         for(int i =1;i<=n;i++)
30.         {
31.                 cin >> v[i] >> w[i];
32.         }       
33.         for(int i = 1;i<=n;i++)
34.         {
35.                 f[0] = 0;
36.         }
37.         for(int i = 1;i<=n;i++)
38.         {
39.                 for(int j =m;j>=v[i];j--)
40.                 {
41.                      f[j] = max(f[j],f[j-v[i]]+w[i]);
42.                 }
43.         }
44.         if(f[m]>=0) cout << f[m] << endl;
45.         else cout << 0 << endl;
47.         return 0;
48. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。