hdu2844（0/1背包+二进制转化）

如果直接按多重背包做会超时，所以要用二进制优化。

模型：

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

办法：

根蒂根基算法

这题目和完全背包题目很类似。根蒂根基的方程只需将完全背包题目的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]默示前i种物品恰放入一个容量为v的背包的最大权值，则有状况转移方程：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

错杂度是O（V*Σn[i]）。

转化为01背包题目

另一种好想好写的根蒂根基办法是转化为01背包求解：把第i种物品换成n[i]件01背包中的物品，则获得了物品数为Σn[i]的01背包题目，直接求解，错杂度仍然是O（V*Σn[i]）。

然则我们期望将它转化为01背包题目之后可以或许像完全背包一样降落错杂度。仍然推敲二进制的思惟，我们推敲把第i种物品换成若干件物品，使得原题目中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换今后的物品。别的，取跨越n[i]件的策略必不克不及呈现。

办法是：将第i种物品分成若干件物品，此中每件物品有一个系数，这件物品的费用和价值均是本来的费用和价值乘以这个系数。使这些系数分别为 1，2，4，...，2^（k-1），n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，若是n[i]为13，就将这种 物品分成系数分别为1，2，4，6的四件物品。

分成的这几件物品的系数和为n[i]，注解不成能取多于n[i]件的第i种物品。别的这种办法也能包管对于0..n[i]间的每一个整数，均可以用若干个系数的和默示，这个证实可以分0..2^k-1和2^k..n[i]两段来分别评论辩论得出，并不难，欲望你本身思虑测验测验一下。

如许就将第i种物品分成了O（log n[i]）种物品，将原题目转化为了错杂度为<math>O（V*Σlog n[i]）的01背包题目，是很大的改进。

以上内容来自背包九讲之多重背包题目

代码：

#include<iostream>
using namespace std;
int f[100005];
int p[105],c[105];
int main()
{
    int i,j,k,n,m,cnt;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
      if(n==0&&m==0) break;
      for(i=0;i<n;i++)
        scanf("%d",&p[i]);
      for(i=0;i<n;i++)
        scanf("%d",&c[i]);
      memset(f,0,sizeof(f));
      f[0]=1;
      for(i=0;i<n;i++)
      {
        cnt=c[i];
        for(k=1;k<=cnt;k<<=1)
        {
          for(j=m;j>=k*p[i];j--)
             f[j]+=f[j-k*p[i]];
          cnt-=k;
        }
        if(cnt)
          for(j=m;j>=cnt*p[i];j--) f[j]+=f[j-cnt*p[i]];
      }
      int sum=0;
      for(i=1;i<=m;i++)
        if(f[i]) sum++;
      printf("%d\n",sum);
 }
 return 0;
}