动态规划-01背包问题之我见

Published on: 2016年8月25日2016年9月24日Author: 陈泱宇 (Yangyu Chen)Comments: 2

Table of Contents

背包问题是信息学奥赛中最经常考的动态规划形式，而01背包又是背包问题的基础。除此之外，背包问题还分为完全背包、多重背包等。

01背包定义如下：

对于1个容积为v的背包和n个物品，这些物品分别有自己的体积Vi，和价值Pi，我们需要有一种算法在背包可以容纳的情况下使装入的物品价值最大。此时n个物品不一定全部放入，背包也不一定装满。

与完全背包不同的是，01背包中是n个物品，而完全背包是n种物品，每种物品可多次放入。

这样的问题为什么不用搜索解决呢？

显然，如果搜索可以完美解决这样的问题，我们自然也就不需要用更好的算法来解决问题了。

通过分析问题，我们可知，对于每个物体都有放入背包和不放入背包两种情况，如果我们使用传统的搜索算法解决这个问题，那么时间复杂度为O(2^n)，数据大了难免超时。

何为动态规划：

动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。继续分析，我们可以通过递推的方式解决该问题，从问题分析出递推式的方法，便是动态规划。

如何用动态规划高效地解决01背包问题？

这是一个01背包常见的递推式

f[i][j]=max(f[i-1][j],f[i-1][j-Vi]+Pi)

其中，i从1到n，j从1到v，条件为j>=Vi

许多人与我一样，在第一次看到这个递推式的时候都十分困惑，全然不知它的含义。

实际上，f[i][j]就是我们在写动态规划程序时所需要开的一个数组，f[i][j]表示放入前i个物品（包含i，但这前i个物品不一定完全放入），背包容积为j时，背包内物品价值和的最大值。

这样，f[i-1][j]显然就是不考虑放入编号为i的物品的情况下背包内物品的最大价值和，而f[i-1][j-Vi]+Pi，便是在只考虑放入前i-1号物品且背包容积为j-Vi时，背包内物品的最大价值和，再放入编号为i的物品，因此加上Pi，也就得到了f[i][j]，即放入前i个物品，背包容积为j时背包内物品的价值的最大值。

对于这个算法，在C语言中通常采用两层for循环解决，以下为C++写法。大家可以根据题目自己修改以符合题目要求。

该方法的时间复杂度为O(n*v)

[sourcecode language=”c”]
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXN 100
#define MAXV 100
//MAXN和MAXV根据题目自行调整
using namespace std;
int main() {
int v;//背包的容积
int n;//物品的数量
cin >> v >> n;
int V[MAXN];//物品的体积（数组下标从1开始）V[i]相当于前文所述的Vi
int P[MAXN];//物品的价值（数组下标从1开始）P[i]相当于前文所述的Pi
for (int i=1;i<=n;i++) cin >> V[i] >> P[i];
int f[MAXN][MAXV];//用于保存递推过程的数组
memset(f,0,sizeof(f));//清零f数组，特别是f[0]的每项元素都必须为0
for (int i=1;i<=n;i++)//处理编号为i的物品放入背包的情况
for (int j=1;j<=v;j++)//枚举背包的容积从1到最大值v
if (V[i] <= j)
//确保该物品可以放入背包（在可能清空别的物品的情况下）
f[i][j] = max(f[i-1][j],f[i-1][j-V[i]]+P[i]);
/*上一行代码特别说明一下:
f[i-1][j]是在本次不放入编号为i的物体情况下背包的内物品的最大价值和。
f[i-1][j-V[i]]是背包在放入编号为i的物品前，
在背包容积只有j-V[i]的情况下背包内物品的最大价值和，
这样就明白为什么要从1开始枚举背包的容积到最大值v了吧。
P[i]不必多言，还要再放上该物品，因此要加上它的价值。
max函数的巧妙在于直接决定放i与否可以取得最大值。
*/
else f[i][j] = f[i-1][j];//这个物品的体积超过了我们目前枚举的背包容积j，因此不放入它，保持上次的原样
cout << f[n][v] << endl;//这里求得的f[n][v]即为所求放入背包内的物品的最大价值和。
return 0;
}
[/sourcecode]