222. 多重部分和问题（挑战程序设计竞赛）

地址 https://www.papamelon.com/problem/222

有 n 种不同大小的数字 a_i，每种各 m_i个。
判断是否可以从这些数字之中选出若干个并使得它们的和恰好为 K

输入
第一行包含两个整数 n 和 K
第二行包含 n 个数表示 a 数组
第三行一行包含 n 个数表示 m 数组
1≤n≤100
1≤a i,m i ≤10^5
1≤K≤10^5
 
输出
输出 Yes 或 No
提示
2021/12/07 加强数据，可尝试重新提交
样例 1
输入
3 17
3 5 8
3 2 2
输出
Yes

解答 dp方法
常规经典动态方案
dp[i][j] 表示前i个物品凑成数目j能否成功 1表示成功 0表示失败
那么

dp[i][j] = max(dp[i-1][j],dp[i-1][j-ai],dp[i-1][a-2*ai]~~~,dp[i-1][j-k*ai]);
但是整个复杂度是O(n*K*m) 超时.
超时代码 TLE

#include <iostream>

using namespace std;

const int N = 105;
int n, K;
int dp[N][100010];
int a[N];
int m[N];

int main()
{
	cin >> n >> K;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> m[i];
	dp[0][0] = 1;
	for (long long i = 1; i <= n; i++) {
		for (long long j = 0; j <= K; j++) {
			if (dp[i - 1][j] > 0)dp[i][j] = 1;
			else {
				for (int k = 1; k <= m[i]; k++) {
					if (j >= (long long)k * a[i]) {
						dp[i][j] += dp[i-1][j - k * a[i]];
						if (dp[i][j] > 0) break;
					}
				}
			}
		}
	}

	if (dp[n][K] > 0) cout << "Yes" << endl;
	else cout << "No" << endl;


	return 0;
}

代码中，第三重循环 for (int k = 1; k <= m[i]; k++)
实际计算的是 第i个数字使用了几次，那么可以考虑使用dp[i][j]记录下第i个数字达到j的和的时候，第i个数字使用了几个，就可以优化掉第三重循环
此时dp[i][j] 表示的意义不再是dp[i][j] 表示前i个物品凑成数目j能否成功 1表示成功 0表示失败
而是 前 i 个数字凑成数目j，第 i 个数字使用了几个

#include <iostream>

using namespace std;

const int N = 105;
int n, K;
int dp[N][100010];
int a[N];
int m[N];


//dp[i][j]表示前i个数字达到j的和时候 第i个数字使用的最小值
int main() {
	cin >> n >> K;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> m[i];
	 
	memset(dp,-1,sizeof dp);
	dp[0][0] = 1;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= K; j++) {
			if (dp[i - 1][j] >= 0) dp[i][j] = 0;
			if (dp[i][j] == -1 && j >= a[i]&&dp[i][j-a[i]]>=0) {
				if (dp[i][j - a[i]] + 1 <= m[i]) {
					dp[i][j] = dp[i][j - a[i]] + 1;
				}
			}
		}
	}

	//cout << dp[n][K] << endl;
	if (dp[n][K] >= 0) cout << "Yes" << endl;
	else cout << "No" << endl;


	return 0;
}