hdu 2844 多重背包

hdu 2844 多重背包

背景：主要是理解了二進制的應用。下次寫背包九應該把代碼模板化一點了，避免錯誤。

思路：F[i]=mas{F[i-kC[i]]+kW[i] | 0 =< k <= Mi}，對於每一個容量都求它的最大價值，由於價值和花費是相等的，所以價值只能小於等於花費，那些價值等於花費的就是輸字能組成這個數。

學習：1.價值和花費都是本身的值得情況，可以用來判斷這些數是否可以組成另一個數。

#include
#include
#include
using namespace std;
int c[109][2],F[100009];

int main(void){
    int n,m;
    while(scanf("%d%d",&n,&m) && n*n+m*m){
        for(int i=0;i < n;i++) scanf("%d",&c[i][0]);
        for(int i=0;i < n;i++) scanf("%d",&c[i][1]);
        memset(F,0,sizeof(F));
        for(int i=0;i < n;i++){
            if(c[i][0]*c[i][1] >= m){
                for(int j=c[i][0];j <= m;j++){
                    F[j]=max(F[j],F[j-c[i][0]]+c[i][0]);
                }
            }else{
                int k=1,key;
                while(k < c[i][1]){
                    key=k*c[i][0];
                    for(int j=m;j >= key;j--) F[j]=max(F[j],F[j-key]+key);
                    c[i][1]-=k;
                    k*=2;
                }
                key=c[i][1]*c[i][0];
                for(int j=m;j >= key;j--) F[j]=max(F[j],F[j-key]+key);
            }
        }
        int count=0;
        for(int i=1;i <= m;i++) if(F[i] == i) count++;
        printf("%d\n",count);
    }
    return 0;
}