首先如果真的用多重背包肯定是TLE的

既然题目要求每种硬币有数量限制，那么

满足要求的方案属 = 无限硬币的方案数 - 不满足要求的方案数

首先用多重背包求出价钱无限硬币时方案数f[i]，那么无限种的方案数为f[s]

再来求不满足的方案数，对于第i中硬币，可以先强制支付（d[i] + 1），那么后面就不能支付这种硬币，则后面还要支付（s - c[i] * d[i - 1])

即： 第i种硬币超过要求的方法数=f[s-c[i]* (d[i]+1)]=f[s−c[i]∗(d[i]+1)]

最后加上4个变量的容斥即可

#include <bits/stdc++.h>

long long n, s;
long long c[10], d[10];
long long ans[1010];
long long f[150010];

void backpag()
{
	f[0] = 1;
	for(long long i = 1; i <= 4; i ++)
	{
		for(long long j = c[i]; j <= 150000; j ++)
		{
			f[j] = f[j] + f[j - c[i]];
		}
	}
}

int main()
{
	std::cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
	backpag();
	for(long long i = 1; i <= n; i ++)
	{
		std::cin >> d[1] >> d[2] >> d[3] >> d[4] >> s;
		ans[i] = f[s];
		for(long long j = 1; j < 16; j ++)
		{
			long long k = 0, num = 0;
			for(long long k2 = 0; k2 < 4; k2 ++)
			{
				if(j&(1<<k2))
				{
					num ++;
					k = k + c[k2 + 1] * (d[k2 + 1] + 1);
				}
			}
			long long fh = 1;
			if(num % 2 == 1)
			{
				fh = -1;
			}
			if(s >= k)
			{
				ans[i]  = ans[i] + fh * f[s - k];
			}
		}
	}
	for(long long i = 1; i <= n; i ++)
	{
		printf("%lld \n", ans[i]);
	}
	return 0;
}

时间复杂度O(mlogn)

#include <bits/stdc++.h>

long long n, s;
long long c[10], d[10];
long long ans[1010];
long long f[150010];

void backpag()
{
	f[0] = 1;
	for(long long i = 1; i <= 4; i ++)
	{
		for(long long j = c[i]; j <= 150000; j ++)
		{
			f[j] = f[j] + f[j - c[i]];
		}
	}
}

int main()
{
	std::cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
	backpag();
	for(long long i = 1; i <= n; i ++)
	{
		std::cin >> d[1] >> d[2] >> d[3] >> d[4] >> s;
		ans[i] = f[s];
		for(long long j = 1; j < 16; j ++)
		{
			long long k = 0, num = 0;
			for(long long k2 = 0; k2 < 4; k2 ++)
			{
				if(j&(1<<k2))
				{
					num ++;
					k = k + c[k2 + 1] * (d[k2 + 1] + 1);
				}
			}
			long long fh = 1;
			if(num % 2 == 1)
			{
				fh = -1;
			}
			if(s >= k)
			{
				ans[i]  = ans[i] + fh * f[s - k];
			}
		}
	}
	for(long long i = 1; i <= n; i ++)
	{
		printf("%lld \n", ans[i]);
	}
	return 0;
}