朴素多重背包。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=10;
int a[M],d[M],f[N];
int main(){
	int n=4,t;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	scanf("%d",&t);
	while(t--){
		int v;
		for(int i=1;i<=n;i++){
			scanf("%d",&d[i]);
		}
		scanf("%d",&v);
		memset(f,0,sizeof(f));
		f[0]=1;
		for(int i=1;i<=n;i++)
			for(int j=v;j>=a[i];j--)
				for(int k=1;k<=d[i];k++)
					if(j>=k*a[i])
						f[j]=f[j]+f[j-k*a[i]];
		printf("%d\n",f[v]);
	}
	return 0;
}

多重背包前缀和优化。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+5,M=10;
int a[M],d[M];
LL f[N],g[N];
int main(){
	int n=4,t;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	scanf("%d",&t);
	while(t--){
		int v;
		for(int i=1;i<=n;i++){
			scanf("%d",&d[i]);
		}
		scanf("%d",&v);
		memset(f,0,sizeof(f));
		f[0]=1;
		for(int i=1;i<=n;i++){
			memset(g,0,sizeof(g));
			for(int j=a[i];j<=v;j++){
				g[j]=g[j-a[i]]+f[j-a[i]];
			}
			for(int j=v;j>=d[i]*a[i];j--){
				g[j]=g[j]-g[j-d[i]*a[i]];
			}
			for(int j=v;j>=a[i];j--){
				f[j]=f[j]+g[j];
			}
		}
		printf("%lld\n",f[v]);
	}
	return 0;
}

如果有人用了二进制拆分过了这题，请告知我并让我膜拜！