【问题描述】

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

【输入】

          第一行 正整数n和w

         以下n行，每行三个正整数为物品的容量、价值和件数，中间用空格隔开。

【输出】

最大价值总和。

【数据规模】

        1<= n<=100, w<=10000, 1<=m[i]<=10000， 1<=c[i],v[i]<=100

 分析：

方法1，朴素算法:f[i,j]表示前i种物品装入容量为j的背包中所能得到的最大价值(0<=k<=min(m[i],j div v[i]))。  

         f[i,j]=max{f[i-1,j-k*c[i]]+k*v[i]}   ,0<=k<=min(m[i],j div v[i])。   

         时间复杂度O(n*V*∑m[i])

方法2，转换为01背包，利用二进制拆分

          假设第i种物品有m[i]件，则可以第i种物品看成m[i]件01背包中的物品，则得到了物品数为Σm[i]的01背包问题，直接求解.时间复杂度：O(V*Σ m[i])。

二进制拆分：

       m[i]=1+2+4+...+2^k+a   (0<=a<2(k+1)，a=n-2^(K+1)+1)

       由于1，2....，2^k可以表示0～2^(K+1)-1中的所有整数（由K位二进制表示），则1，2，4，...，2^k，a可以表示出0～m[i]的所有整数（a与0～2^(K+1)-1的所有整数相加，可以表示出2^(K+1)~n的所有整数）。

       m[i]可以分解出log(m[i])+1个背包，则时间复杂度为O(V*∑log(m[i]))

方法3，单调队列

    方法1中f[i,j]=max{f[i-1,j-k*c[i]]+k*v[i]}   ,0<=k<=min(m[i],j div v[i])。

   令a[j]=f[i-1,j*c[i]],k=min(m[i],j div v[i]则有

   f[i,(j+k)*c[i]]=max{f[i-1,(j+k)*c[i]-k*c[i]]+k*v[i],f[i-1,(j+k)*c[i]-(k-1)*c[i]]+(k-1)*c[i],...,f[i-1,(j+k)*c[i]+(k-k)*c[i]]+(k-k)*c[i] 

                       =max{f[i-1,j*c[i]]+k*v[i],f[i-1,(j+1)*c[i]]+(k-1)*c[i],...f[i-1,(j+k)*c[i]]}

                       =max{a[j]+k*c[i],a[j+1]+(k-1)*c[i],...,a[j+k]}

这样还是不方便计算，令b[j]=a[j]-j*c[i]

    则有f[i,(j+k)*c[i]]=max{b[j]+(j+k)*c[i],b[j+1]+(J+K)*c[i],...,b[j+k]+(j+k)*c[i]}

                               =max{b[j],b[j+1],...,b[j+k]}+(j+k)*c[i]

这样就可以使用单调队列来求解了。时间复杂度O(nV)