浅谈用一维数组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逐渐递增打表，所以递归式应该修改为

$$f[i][y]= \begin{cases} max\{f[i-1][y],f[i-1][y-wi]+pi\},y>=wi//能放入物品i\\ f(i-1，y),0<=y<wi \end{cases}$$

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

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

现在改为i从1开始打表

上表中具体的数值不用在意，只是我们要理解打表的流程，上图中都是先对第一行对应的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是从小到大递增还是从大到小递减进行打表求解？

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

$$f[y]=max\{f[y], f[y-wi]+pi\}$$

我们假设此时还是沿用之前的思路，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©表示的都是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©并且更新f©为i=2的值，此时f(0)~f(c-1)还是i=1的情况f©是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©而已，所以两个方法均可以使用，但是一维方法更简单高效。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章