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;
}