浅谈用一维数组dp解决0/1背包问题 - 雨中的博客

本篇博客主要是受《牛客网入学考试》题目启发,拓展浅谈一下自己对于从用二维数组dp解决0/1背包问题优化成用一维数组dp解决0/1背包问题的算法理解。

用二维数组dp解决0/1背包问题

其实这个问题在数月前曾总结过一次,在《动态规划》中我曾总结过使用二维数组打表解决0/1背包问题的方法,并且也介绍了使用元组法尝试优化二维数组dp的思路,但是并没有给出具体的实现。这里我想重新定义一下二维数组dp解决0/1背包的问题。在之前的博客中我们介绍到打表时使用的函数定义如下:

但是这貌似和大多数人的二维数组的板子不太一样,因为这里我定义的是f(i,y)为背包剩余容量为y时,在物品i~n中选取。然后每次打表都是让i从n开始递减到1,所以递归式是由后向前即根据i+1推出i。这里我重新修正定义f(i,y)函数含义为背包剩余容量为y时,在物品1~i中选取。那么我们在打表时,应该是让i从0逐渐递增打表,所以递归式应该修改为

即对于每一行i的表格,要根据前一行i-1来推出下一行第i行的数值(之前是根据前一行i+1来推出下一行第i行的数值)。但是我们发现重定义完f(i,y)函数以后实际上本质上打表思路还是一样的,都是对于不同的i各自对应着表格的一行,然后对于每一行又会根据y的值对应不同的效益值。只是打表的行顺序变了而已,如下图:

对于之前的i从n开始的打表:

现在改为i从1开始打表

i\y 0 1 2 3 4 5 6 7 8 9 10
1 0 0 6 6 6 6 6 6 6 6 6
2 0 0 6 6 9 9 9 9 9 9 9
3 0 0 6 6 6 6 9 9 9 9 14
4 0 0 6 6 6 6 9 9 9 9 14
5 0 0 6 6 6 6 12 12 12 12 15

上表中具体的数值不用在意,只是我们要理解打表的流程,上图中都是先对第一行对应的i不同的y进行打表,然后在后面的行中使用递归式进行打表。但是无论是哪种f(i,y)的定义,我们发现在打表时都是默认的y从0到最大值c递增对应的不同情况打表。这是因为二维数组dp时,递归式中的右边项总是来自已经存储于前一行中的数值。所以y是正序递增从0~c打表即可并无问题。板子如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//代码转载于https://blog.csdn.net/weixin_41061962/article/details/80319436,非常感谢
#include<bits/stdc++.h>
using namespace std;
struct KNAP
{
int w; //weight;
int v; //value,or portfolio;
};
//二维的方式
void solveKPd(vector<KNAP> cknap, vector<vector<int> > &dp, int n, int Tw)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j <=Tw; j++)
{
//先检验能否装入物品i
if (j<cknap[i].w) dp[i+1][j] = dp[i][j];
//j是每一个子问题的w上界,这里与整体的Tw无关
//然后根据递归取最大值,其中这些右边的数值都来自于表的前一行
else if (dp[i][j] < dp[i][j - cknap[i].w] + cknap[i].v)
dp[i+1][j] = dp[i][j - cknap[i].w] + cknap[i].v;
else
dp[i+1][j] = dp[i][j];
}
}
cout << dp[n][Tw] << endl;
}
int main()
{
int Tw; int n;
cin >> Tw >> n;
vector<KNAP> cknap;
for (int i = 0; i < n; i++)
{
KNAP temp;
cin >> temp.w >> temp.v;
cknap.push_back(temp);
}
vector< vector<int> > dp(n+1, vector<int>(Tw+1,0));
solveKPd(cknap, dp, n, Tw);
system("pause");
return 0;
}

用一维数组dp解决0/1背包问题

现在我们思考一下用一维数组dp解决0/1背包问题,那么我们使用一维数组的思想就是每次打印第i行时都能够刚好把第i-1行的数据覆盖掉,这样,就不是二维打表了,永远是在一个一维数组中进行。所以很明显f(i,y)函数中的i就不需要了,因为永远只有一行。所以变为了f(y),即只有一个自变量参数背包剩余容量y。那么我们知道无论如何,第i行的数据肯定是需要与来自于第i-1行的数据比较的,只是在一维数组的方法中,使用完这个第i-1行数据以后就用新的第i行数据覆盖掉了。所以我们在推导第i行的数据时要保证他需要的第i-1行数据还存在。此时我们可以遇见到一个问题,即y是从小到大递增还是从大到小递减进行打表求解?

首先我们知道递归式应该如下了:

我们假设此时还是沿用之前的思路,y从小到大开始递增进行打表,那么板子应该如下:

1
2
3
4
5
6
7
8
9
//此时每次遍历i就是打印一行
for (i = 1; i <= n; i++){
//注意,此时y还是从小到大
for (y = 0; y <=c&&y>=w[i]; y++){
//右边的都是第i-1次循环的结果
f[y] = max(f[y], f[y - w[i]] + p[i]);
}
}

我们发现有点bug,就是假设现在打印完了i=1情况下的所有f(y)的值,那么此时f(0)~f(c)表示的都是i=1情况下的值(注意此时f函数的自变量参数为背包剩余容量y)。那么如果按照递增打印,此时我们要打印i=2情况了,y从0开始根据推导式求得了i=2时的f(0),那么此时f(0)就要更新为i=2的情况了,所以此时一维数组中f(0)是对应的i=2,其他f(2)~f(n)对应的还是i=1的情况,那么此时我们要求解i=2情况下的f(1)可能会用到i=1情况下的f(0)(比如此时根据递归式f(1)=max[f(1),f(1-w[1])+p1)],恰巧后一项的f(1-w[1])=f(0)),那么就会用到i=1时的f(0))。但是我们惊讶的发现此时f(0)已经不是i=1的情况了,而是更新成了i=2的情况了,所以此时i=2情况下的f(1)就不能求解了因为缺少上一行i=1时的f(0)值。所以y正序打印是不行的,我们需要让y倒序打印,即板子修改为:

1
2
3
4
5
6
7
8
//此时每次遍历i就是打印一行
for (i = 1; i <= n; i++){
//注意,此时y还是从大到小
for (y = c; y>=w[i]; y--){
//右边的都是第i-1次循环的结果
f[y] = max(f[y], f[y - w[i]] + p[i]);
}
}

此时我们再分析一下,当i=1这行打完表以后,我们按照上面的代码,是先根据i=1的值推导出了i=2情况下的f(c)并且更新f(c)为i=2的值,此时f(0)~f(c-1)还是i=1的情况f(c)是i=2的值,我们要打印f(c-1)了,可能f(c-1)会用到i=1时的f(c-3),我们发现此时f(c-3)确实还是i=1的值,恰好可以用。所以y从大到小打印刚好可以使用到之前的值,并且更新以后的值不会影响后面的推导。

最后我们总结一句话,就是对于f[y], 它要调用的f[y-w[i]]一定是第i层循环还没有更新过的, 换言之, f[y-wi]只有可能是第i-1层存储的数据。这就是y要逆序打印的原因,至于i可以正序也可以逆序,只是对应着不同的f函数的定义。

核心板子

因此一维数组dp解决0/1背包板子如下:

1
2
3
4
5
6
7
8
//此时每次遍历i就是打印一行
for (i = 1; i <= n; i++){
//注意,此时y还是从大到小
for (y = c; y>=w[i]; y--){
//右边的都是第i-1次循环的结果
f[y] = max(f[y], f[y - w[i]] + p[i]);
}
}

思考:物品能否放入背包的特判放到了哪里?

此时物品能够放入背包的特判放到了第二个for循环中了,这也是巧合之处。只有满足了特判条件才能够进行下面的更新,并且此时你可能会有疑虑,一旦不满足了情况就会退出y循环,那么这行值是否会出现还未打印完的情况,即前面还是未更新的值,此时我们细想一下,未更新的值实际上也可以看成是更新的值了,只是由于为装入物品i所以,值并未变化,直接沿用之前的i-1的值即可了。所以二维与一维最大的区别有

  1. 二维y是从小到大和从大到小均可以,但是一维y必须从大到小逆序
  2. 二维数组中的递归式目的是填写值,必须每一个位置都重新通过递归式进行填值,但是在一维方法中递归式的目的是更新值,如果不满足物品i可以装入的条件,那么前面的所有值均不会变化,也就无需更新,直接退出循环即可。

思考:二维方法与一维方法的结果特点对比?

二维方法中我们求解完以后是一张完整的表格,他里面填写了对于不同的i不同的y情况时的效益值,但是在一维方法中最终我们求得的是一个向量,只保存了i=n,不同y情况的效益值,一维方法的其他i情况的值在多次推导和更新中被更新的值覆盖了。但是,最终我们需要的只是满足题干的f(n,c)或者f(c)而已,所以两个方法均可以使用,但是一维方法更简单高效。




©2020 - 2021 By wenchong
津ICP备2021004286号

本站总访问量为 访客数为

本站使用 Volantis 作为主题|借助hexo强力驱动|由腾讯云提供云服务