dp背包

#include<bits/stdc++.h>
using namespace std;


    /*初始化的细节问题 我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。


    有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了 f[0]为 0 其它 f[1..V]均设为-∞，这样就可以保证最终得到的 f[N]是一种恰好装满背包
的最优解。
    如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 f[0..V]全部设为 0。


    为什么呢？可以这样理解：初始化的 f 数组事实上就是在没有任何物品可以放入 背包时的合法状态。
如果要求背包恰好装满，那么此时只有容量为 0 的背包可能 被价值为 0 的 nothing“恰好装满”，其它容
量的背包均没有合法的解，属于未 定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那
么任何 容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状 态的值也就全部为 0 了。*/



//01背包
void ZeroOnePack(cost,weight)
{
    for(int v=V;v>=cost;v--)
        f[v]=max(f[v],f[v-cost]+weight);
}

    for i=1...N
        ZeroOnePack(c[i],w[i]);


//完全背包
void CompletePack(cost,weight)
{
    for(int v=cost;v<=V;v++)
        f[v]=max(f[v],f[v-cost]+weight);

}

    for i=1...N
        CompletePack(c[i],w[i]);


//多重背包

//方法一：每种物品分解为多个  01背包求解
void MultiplePack(cost,weight,amount)
{
    for(int v=V;v>=cost;v--)
        for(int k=0;k<amount;k++)
            f[v]=max(f[v],f[v-cost]+weight);
}

    for i=1...N
        MultiplePack(c[i],w[i],n[i]);


//方法二：二进制优化
void MultiplePack(cost,weigt,amount)
{
    if(cost*amount>=V)//全部装不下  当完全背包 可取任意多个
        {
            CompletePack(cost,weight);
            return ;
        }

    int k=1;
    while(k<amount)
    {
        ZeroOnePack(k*cost,k*weight);
        amount-=k;
        k<<1;//k*=2;
    }
    ZeroOnePack(amount*cost,amount*weight);
}