多重背包二进制优化
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int maxn=111; int v[maxn],num[maxn]; int dp[100000+10]; int ans[100000+10]; int main() { int i,j,k,n,m; while(~scanf("%d%d",&n,&m)) { if(n==0&&m==0) break; for(i=1;i<=n;i++) scanf("%d",&v[i]); for(i=1;i<=n;i++) scanf("%d",&num[i]); memset(dp,0,sizeof(dp)); dp[0]=1; for(i=1;i<=n;i++) { int number=num[i]; int k=1; while(k<number) { number=number-k; for(j=m;j>=k*v[i];j--) if(dp[j-k*v[i]]==1) dp[j]=1; k=k*2; } for(j=m;j>=number*v[i];j--) if(dp[j-number*v[i]]==1) dp[j]=1; } int ans=0; for(i=1;i<=m;i++) if(dp[i]) ans++; printf("%d ",ans); } return 0; }