01背包问题解法
原创：Jiau机器感知8月7日
未经许可，禁止转载
1.定义
我们有$N$种物品，物品$i$的重量为$w[i]$，价格为$p[i]$。我们假定所有物品的重量和价格都是非负的，背包所能承受的最大重量W，如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。
2.二维动态规划解法
二维动态规划其实就是填表，表格中的值表示能获得的最大总价值，表格如下：
现在我们分析动态规划中的状态转移，假设当前待求状态为table[i][j]，其中，$i$表示第$i$个物品，$j$表示当前背包容量，由于是01背包问题，即一个物品只能选或者不选，也即当前最优解的可能有两种，即选与不选，对应的总价值分别为：table[i-1][j]、table[i-1][j-w[i]]+v[i]，解释如下：
当不选择第$i$件商品时，当前最大价值就和状态$i-1$，容量为$j$时的最优解一样；当选择第$i$件物品时，当前最大价值就状态$i-1$，但容量为$j-w[i]$，再加上当前物品价值$v[i]$时的价值，由此可得，该问题的状态转移方程如下：
table[i][j]=max(table[i-1][j],table[i-1][j-w[i]]+v[i])
有了这个状态转移方程之后，我们就可以写程序了，示例程序如下：
//totalweight
defineN(7)
inttable[N+1][W+1]={0};
intvalue[N+1]={0,12,10,8,11,14,7,9};
intweight[N+1]={0,4,6,5,7,3,1,6};
voidknapsack()
{
intk,w;
for(k=1;k=N;k++){
for(w=1;w=W;w++){
if(weight[k]w){
table[k][w]=table[k-1][w];
}else{
intvalue1=table[k-1][w-weight[k]]+value[k];
intvalue2=table[k-1][w];
if(value1value2){
table[k][w]=value1;
}else{
table[k][w]=value2;
}
}
}
}
}
运行结果如下，对比网图可知，结果完全相同：
3.最优解回溯
通过上面的方法可以求出背包问题的最优解，但还不知道这个最优解由哪些商品组成，故要根据最优解回溯找出解的组成，根据填表格时的规则，反推可知：
a.如果table[i][j]==table[i-1][j]，这说明第$i$件商品没有被选择，则上一步就是在table[i-1][j]的位置处；
b.如果table[i][j]!=table[i-1][j]，说明选择了第$i$件商品，再根据table[i][j]=table[i-1][j-w[i]]+v[i]可得到上一个位置为table[i-1][j-w[i]]位置处；
c.如此反复找到i=0为止。
示例代码如下：
voidshow_track()
{
vectorpairint,inttrack;
inti=N,j=W;
while(i0){
if(table[i][j]==table[i-1][j]){
i--;
}else{
_back(make_pair(i,j));
intw=weight[i];
j-=w;
i--;
}
}
for(inti=0;();i++){
couttrack[i].first'';
}
}
4.复杂度分析
根据程序分析可知，我们需要填的表格数量为$N*W$，因此时间复杂度和空间复杂度都是$O(N*W)$，因为要遍历完所有的可能性才可能得到最优解，而不像有序数组一样可以二分法或者什么的，所以时间复杂度没法优化了，但空间复杂度还是可以优化的，因为我们每次更新只与上一时刻状态有关，所以不需要保留这么多时刻的状态，空间复杂度可以优化到$O(W)$，首先分析上一步的核心代码：
for(w=1;w=W;w++){
for(k=1;k=N;k++){
if(weight[k]w){
table[k][w]=table[k-1][w];
}else{
intvalue1=table[k-1][w-weight[k]]+value[k];
intvalue2=table[k-1][w];
}
可以看出，核心代码部分，每次更新仅与上一时刻状态有关，对应到table中就是，每次更新只与table的一个行数据有关，这也就是空间复杂度为什么能够优化为$O(W)$的原因，如果简单的优化成如下代码：
for(w=1;w=W;w++){
for(k=1;k=N;k++){
if(weight[k]w){
table[w]=table[w];
}else{
//需要w前方的w-weight[k]处的值
intvalue1=table[w-weight[k]+value[k];
intvalue2=table[w];
table[w]=;
}
上述代码不会得到正确的结果，为什么呢？行扫描我们是从左到右进行的，而我们需要取$w-weight[k]$，即$w$左边的值，而我们却从左边开始更新的，那么就出现了我们需要的值被开始的更新覆盖了，得到的就是当前时刻的值了，不是期待的上一时刻的值，很显然不可能的得到正确的结果了，为了避免这种覆盖现象发生，我们可以通过反向扫描更新，即从右到左更新，这样更新的位置确定不会被左方的需要，就可以得到正确的结果了，代码如下：
voidknapsack_optimization()
{
//仅使用table中第一行
intk,w;
for(k=1;k=N;k++){
for(w=W;w=1;w--){
if(weight[k]w){
table[0][w]=table[0][w];
}else{
intvalue1=table[0][w-weight[k]]+value[k];
intvalue2=table[0][w];
if(value1value2){
table[0][w]=value1;
}else{
table[0][w]=value2;
}
}
}
}
}
5.总结
01背包问题解法使用的是二维动态规划进行求解的，朴素二维的动态规划时间复杂度和空间复杂度都是$O(N*W)$，而经过分析代码可以看出，状态转移时，当前时刻状态只与上一时刻的状态有关，所以空间复杂度可以优化到$O(W)$，在优化代码是需要注意的是：需要改变行更新顺序，为了避免新的状态覆盖上一时刻的状态，需要从右到左进行更新状态；有了最优解之后就是回溯最优解，方法步骤遵循上述步骤即可。
附录
