背包基础问题

01背包（ZeroOnePack）:有N件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

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

4件物品，重量和价值如下，背包的重量为10,

01背包代码：

//W[i]表示重量，v[i]表示价值,背包容量为gint f[x+1];//f[x]背包容量为x的最大价值for(int i=0;i<n;i++)     for(int j=g;j>=w[i];j--)          f[j]=max(f[j],f[j-w[i]]+v[i]);完全背包代码：
for(int i=0;i<n;i++)    for(int j=w[i];j<=g;j++)         f[j]=max(f[j],f[j-w[i]]+v[i]);01背包采用j=g;j>=w[i];j--这样可以避免一个物品被多次使用到。例如：若使用w[i]→g，被使用到的f[j-w[i]]的值可能包含这个物品w[i]，从g→w[i]保证了引用的f[j-w[i]]为没有用到物品w[i]。
完全背包恰好可以使用这个顺序，因为物品可以随意使用只要使f最大即可
初始化分两种情况：        1、如果背包要求正好装满： f[0] = 0, f[1~w] = -INF(若求最小价值，则f[1~w] = INF)
(因为此时未被装满的话是-inf上+正数没影响，f[0]=0，当j=w[i]时，f[j]=f[0]+v[i]，这相当于每件物品分别装满)
        2、如果不需要正好装满： f[0~w] = 0;  
最终结果：f[w] 即为所求  
多重背包(MultiplePack):有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
 
多重背包转换成01背包问题就是多了个初始化，把它的件数C用二进制分解成若干个件数的集合，这里面数字可以组合成任意小于等于C的件数，而且不会重复，之所以叫二进制分解，是因为这样分解可以用数字的二进制形式来解释        比如：7的二进制7 = 111它可以分解成001 010 100这三个数可以组合成任意小于等于7的数，而且每种组合都会得到不同的数，15 = 1111可分解成0001  0010  0100  1000四个数字        如果13 = 1101则分解为 0001 0010 0100 0110前三个数字可以组合成 7以内任意一个数，即1、2、4可以组合为1——7内所有的数，加上0110 = 6 可以组合成任意一个大于6小于等于13的数，比如12，可以让前面贡献6且后面也贡献6就行了。虽然有重复但总是能把13以内所有的数都考虑到了，基于这种思想去把多件物品转换为，多种一件物品，就可用01背包求解了。
        int n,g;        cin>>g>>n;        int count=0;        for(i=0;i<=n-1;i++)        {            cin>>w[i]>>v[i]>>c[i];//对该种类的c[i]件物品进行二进制分解，对于13              for(j=1;j<=c[i];j=j*2)//0001,0010,0100,...依次分解            {                w0[count]=w[i]*j;                v0[count]=v[i]*j;                count++;                c[i]=c[i]-j;            }            if(c[i]>0)//对剩余的1000进行储存            {                w0[count]=w[i]*c[i];                v0[count]=v[i]*c[i];                count++;            }        }1.//经过上面对每一种物品的分解，  2.        //现在v0[]存的就是分解后的物品价值  3.        //w0[]存的就是分解后的物品重量  4.        //count就相当于原来的n  5.        //下面就直接用01背包算法来解          memset(f,0,sizeof(f));        for(i=0;i<=count-1;i++)            for(j=g;j>=w0[i];j--)            f[j]=max(f[j],f[j-w0[i]]+v0[i]);