首頁 Uva Problems

# 題目: UVa 1213 - Sum of Different Primes

# 題目說明

求將 K 個小於等於 N 的質數相加後等於 N 的方法數量

例如:
N = 24 、 K = 3
則答案有 2 種

INPUT:
每筆測資輸入兩個整數 N 、 K
當 N 與 K 為 0 時結束程式

OUTPUT:
輸出 dp[N][K]

# 解題方法

此題為 knapsack problems (背包問題)

先將 <=1120 的所有質數找出，存入 prime

定義一個 dp[i][j]
i 為當前的 N ，也就是能取到的最大數字
j 為相加的質數數量

dp[i][j] += dp[i - prime[k]][j - 1]
代表將 dp[i - prime[k]][j - 1] 加上當前的 prime[k]
將其所有可能加總，即為 dp[i][j]

避免資料被覆蓋，所以需要從 1120 往回做動態規劃

# 參考程式碼

#include <iostream>
#include <vector>;
using namespace std;
int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int N, K;
	vector<int> prime;
	vector<bool> vis(1121);
	int dp[1121][15] = {};
	// find prime number
	prime.emplace_back(2);
	for (int i = 3; i <= 1120; i += 2) if (!vis[i])
	{
		prime.emplace_back(i);
		for (int j = i * 2; j <= 1120; j += i) vis[j] = true;
	}
	// dp (knapsack)
	dp[0][0] = 1;
	for (int k = 0; k < prime.size(); ++k) for (int i = 1120; i >= prime[k]; --i)
		for (int j = 14; j >= 1; --j) dp[i][j] += dp[i - prime[k]][j - 1];
	while (cin >> N >> K, N && K) cout << dp[N][K] << "\n";
	return 0;
}
# 參考資料
https://github.com/morris821028/UVa/blob/master/volume012/1213%20-%20Sum%20of%20Different%20Primes.c
https://blog.csdn.net/mobius_strip/article/details/73657860