多重背包板子。具体可以参考 再谈单调队列优化 & 背包九讲.
这里再仔细讲一下二进制拆分的具体做法。
假设你有 (7) 个价值为 (v_i)，重量为 (w_i) 的物体。现在考虑把多重背包变成 (01) 背包。如果我们把 (1) 个这样的物体看做第一组，(2) 个这样的物体看做第二组，(4) 个这样的物体看做第三组。你会发现用这三组进行的 (01) 背包可以覆盖原来的情况（从二进制上很好理解），并且本来枚举 (7) 次，现在你不用去枚举这三组的所有情况（否则不白优化了），而是用 (3) 次动态规划解决问题。
如何把若干个这样的物体看做一组？让其 (v,w) 跟随个数的增大而同比例增大即可。
于是对于 ({ v_i , w_i , c_i }) 的物体，必定可以将其分为 (log c_i) 个物体。
现在你对 (n log sum c) 个物体，(m) 重量做 (01) 背包。用朴素动态规划。假设 (T) 组数据，则：
时间复杂度：(mathcal{O}(Tnm log sum c)).
本题理论跑满（不妨设 (T=5)）可达 (8 imes 10^8)，理论不可过。但无需卡常数，实际即可跑过。
当然也可以用单调队列优化，可以将其复杂度降至 (mathcal{O}(Tnm))，但这里不多详解，可以到我的背包九讲里去看。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=1e6+1;
inline int read(){char ch=getchar(); int f=1; while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0; while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}
inline void write(int x) {
if(x<0) {putchar('-');write(-x);return;}
if(x<10) {putchar(char(x%10+'0'));return;}
write(x/10);putchar(char(x%10+'0'));
}
int n,m,a[N],c[N];
int w[N];
bool f[N];
int main() {
n=read(); m=read();
while(n && m) {
memset(f,0,sizeof(f)); int ans=0;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) c[i]=read();
int cnt=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=c[i];j<<=1) w[++cnt]=j*a[i],c[i]-=j;
if(c[i]) w[++cnt]=c[i]*a[i];
} f[0]=1;
for(int i=1;i<=cnt;i++)
for(int j=m;j>=w[i];j--)
f[j]|=f[j-w[i]];
for(int i=1;i<=m;i++) ans+=f[i];
printf("%d
",ans);
n=read(),m=read();
}
return 0;
}