完全背包

Ruby_Z · 2019-07-26 08:49:14 · 个人记录

完全背包

（背包九讲中第二讲的解释和代码）

背包九讲

1.题意

基本与01背包相同，但是每种物品可选无限次

2.思路

与01背包相似，易得

f[i][j]=max{f[i-1][j-k*v[i]]+w[i]} (0<=k*v[i]<=V)

可以看出时间复杂度是比较高的

3.简单优化

若物品 i ， j 满足 v [ i ] < = v [ j ] 且 w [ i ] > = w [ j ]

则一定可以去掉 j

另一种是把体积超过V的去掉（一定不选），然后计算相同体积价值最大的是哪个

或者利用二进制思想将每个物品拆成体积为 v [ i ] × 2 ^ k , 价值为 w [ i ] × 2 ^ k 的多件物品，做01背包

4.优化

还是利用滚动数组，这次保证当前状态是由同一阶段状态推出即可

（拿 k 个同种物品可以通过拿 k - 1 个同种物品的状态转移，先拿 k - 1 再拿一个就是 k 个物品）

for(int i=1;i<=n;i++)
    for(int j=v[i];j<=V;j++)
        f[j]=max(f[j],f[j-v[i]]+w[i]);

注意这次第二个 for 循环的顺序与01背包正好相反

因为这次每种物品可以拿多个，所以固定 i 时，j 可以由同阶段的 f [ ] 值推出

另外两个 for 循环的顺序可以颠倒，可能会带来常数上的优化

5.抽象为函数

这一部分主要是为了调用方便，因为接下来的多次背包需要调用完全背包

void CompletePack(int v,int w)
{
    for(int j=v;j<=V;j++)
        f[j]=max(f[j],f[j-v]+w);
}

（直接 define 也可以哒）