itdef

地址 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;
}