动态规划之背包问题

01背包

有N件物品和一个容量为V的背包。第i件物品的费用为c[i]，价值为w[i]
求解将哪些物品装入背包可使价值总和最大？

基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，要么选择放，要么不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可获得的最大价值
则状态转移方程为：
$$f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i])$$
即若只考虑第i件物品的策略(放与不放)，那么久转化为一个只牵扯前i-1件物品的问题
若不放第i件物品，那么就转化为前i-1件物品放入容量为v的背包获得的最大价值，为f[i-1][v]
若放第i件物体，那么问题就转化为前i-1件物品放入剩下的容量为v-c[i]的背包中，获得的最大
价值为f[i-1][v-c[i]]再加上放第i件物品获得的价值w[i]。

优化空间复杂度

以上方法的时间和空间复杂度均为O(V*N)，其中空间复杂度可以优化为O(V)
f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推出来的，即f[i][v]只与前一状态有关
可以用一维数组 f[v]来表示容量为v时的最大价值，f[v]=max(f[v],f[v-c[i]]+w[i])
这样v需要从大到小逆序更新，现在的f[v-c[i]]相当于原来的f[i-1][v-c[i]]，若v从小到大顺序
更新，f[i][v]就由f[i][v-c[i]]推得，与题意不符，但它确实完全背包的解决方案

01背包代码

void zeroOne(int cost,int weight){

    for(int i=V;i>=v[i];i--)
        f[i]=max(f[v],f[v-c[i]]+w[i]);
}

初始化细节问题

若没有要求必须将背包装满，而是只希望价值尽量大，初始化时应该将f[0…V]全设为0
若要求背包恰好装满，则要将f[0]=0，其他赋为负无穷，因为背包为0可由0件物品恰好装满，得到的价值为0

完全背包

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

基本思路

这个问题类似于01背包，所不同的是每种物品有无限件。从每种物品的角度考虑，与它相关的策略并不是取与不取，而是取0件、1件、2件…等很多种情况。如果仍然用01背包求解，f[i][v]为将前i种物品放入容量为v的背包所得的最大价值，则状态转移方程为：
$$f[i][v]=max(f[i-1][v-k*c[i]]+k*w[i]) (0 \leq k*c[i] \leq v)$$
但是这个复杂度很高，可以简单的优化一下
$若两件物品i,j满足c[i] \leq c[j],w[i] \geq w[j],则将物品j可以去掉，不用考虑$
但是这样最坏情况下效率还是很低，一个更高效的方法为转化为二进制思想的01背包
将第i种物品拆成费用为c[i]*2^k,价值为w[i]*2^k的若干件物品
但是有一个最高效的方法：前面01背包中已提到，状态转移方程为
$$f[i][v]=max(f[i-1][v],f[i][v-c[i]]+w[i])$$

完全背包代码

void complete(int cost,int weight){

    for(int i=v[i];i<=V;i++)
        f[i]=max(f[v],f[v-c[i]]+w[i]);
}

多重背包

有N种物品和一个容量为V的背包。第i种物品的数量为n[i],的费用为c[i]，价值为w[i]
求解将哪些物品装入背包可使价值总和最大？

基本思路

多重背包和完全背包很类似,即对于第i件物品，有n[i]+1种策略，取0件、1件、2件…n[i]件
状态转移方程为 $ f[i][v]=max(f[i-1][v-k*c[i]]+k*w[i]) (0 \leq k \leq n[i]) $
复杂度也很高，为了高效的解决，可以转化为完全背包和二进制思想的完全背包

多重背包代码

void multiple(int cost int weight,int amount){

    if(cost*amount>=V){
        complete(cost,weight);
        return ;
    }
     for(int k=1;k<amount;k*=2){  
        zeroone(k*cost,k*weight);  
        amount-=k;  
    }  
    zeroone(amount*cost,amount*weight);  
}