[C++知识库]Coins---多重背包+bitset+二进制优化

Coins—多重背包+bitset+二进制优化

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <bitset>
using namespace std;
//#define int long long
const int N = 100010,INF=0x3f3f3f3f;

int n,m;
bitset<N>f;
int cnt[110],w[110];
signed main()
{
    while(scanf("%d %d",&n,&m),n||m)
    {
    	f.reset();
    	for(int i=0;i<=m;i++)f[i]=0;
    	f[0]=1;
    	for(int i=1;i<=n;i++)scanf("%d",w+i);
    	for(int i=1;i<=n;i++)scanf("%d",cnt+i);
    	for(int i=1;i<=n;i++)
    	{
    		for(int k=1;k<=cnt[i];k*=2)
    		{
    			f|=f<<(w[i]*k);
    			cnt[i]-=k;
			}
			f|=f<<(w[i]*cnt[i]);
		}
		int res=0;
		for(int i=1;i<=m;i++)if(f[i])res++;
		printf("%d\n",res);
	}
}