Tuesday, June 19, 2012

动态规划之背包问题【2】

背包问题的另一个代表是完全背包问题,就是可放的物品有无穷多个,你可以重复选择!所以问题的描述就变成了:

有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

如果按传统01背包的思路来考虑,我们可以得到如下的状态转移方程:

f[i][v] = max{ f[i-1][v-k*c[i]]+k*w[i] }, where 0<=k*c[i]<=v;
上面的这个方程相当于在01背包原有基础上,在加上一个循环,将第i个物品可能放的数目都实验一遍!所以对应的状态还是O(VN)个,但每个状态的求解时间变成了O(v/c[i]),总的复杂度变成了O(V*Sum(V/c[i]))!
对于上面的这种情况,我们可以考虑一个简单的优化办法!
将符合c[i]<=c[j],w[i]>=w[j]的物品删掉!这个优化显然正确,因为我们总能用c[i]来替换c[j],得到的结果至少不比原来的结果差!但要注意,我们不能用密度来替换,那样就犯了贪心算法的错误!例如三个物品:c1=49,c2=50,c3=51;v1=1,v2=2,v3=2.5…明显得不到正确结果!
下面说两个复杂点的优化方法,我给他们起了两个名字方便大家记忆:一个是平铺,一个是2进制编码!下面我分别分析一下!


  • 平铺的核心思想就是将物品提前重复,因为第i个物品最多放v/c[i]次,那我们就重复放v/c[i]个物品在可选的物品集合里,这样,虽然物品的数量大了,而且有重复,但我们就能直接用01背包的算法求解了!

  • 2进制编码的核心思想跟十进制转二进制数类似。将第i个物品转化为若干个物品,其中新的价值为w[i]*2^k;新的费用为c[i]*2^k,其中k满足c[i]*2^k<=V。这样,不管我们重复选几个c[i],都会有一个或多个新物品的组合与之对应!并可以轻松的求出c[i]需要的次数!
下面在介绍一个O(VN)算法!

这个算法使用一维数组,先看伪代码:

for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+weight}

你会发现,这个伪代码与01背包空间优化算法伪代码只有v的循环次序不同而已。按照v=V..0的逆序来循环,是为了保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说,这正是为了保证每件物品只选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第i种物品”这种策略时,却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]],所以就可以并且必须采用v=0..V的顺序循环。上面的这个思路,可以得到一个改进的状态转移方程,如下:

f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}

No comments:

Post a Comment