# 題目: UVa 11517 - Exact Change

# 題目說明

給一個price與N個面額，求這些面額加總最接近price (大於等於) 的值與面額數量

---

INPUT:
第一行輸入一個整數T，代表測資數
每筆測資輸入兩個整數price與N
接下來有N個整數，代表面額

---

OUTPUT:
輸出面額加總最接近price (大於等於) 的值與面額數量

# 解題方法

以一個sum來判斷最少需要做到多少，也就是所有大於sum的面額及加總都忽略

轉移方程為dp[j] = min(dp[j], dp[j - coin[i]] + 1)
代表sum為j時組成的面額數量
由後面開始做是因為每個面額只能用一次

# 參考程式碼

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);

	int T, price, N;
	cin >> T;

	while (T-- && cin >> price >> N)
	{
		vector<int> dp(20001, INT_MAX / 2);
		vector<int> coin(N);
		int sum = 0;
		dp[0] = 0;

		for (int i = 0; i < N; ++i)
		{
			cin >> coin[i];
			if (sum < price) sum += coin[i];
		}

		for (int i = 0; i < N; ++i) for (int j = sum; j >= coin[i]; --j) 
			dp[j] = min(dp[j], dp[j - coin[i]] + 1);
		
		while (dp[price] == INT_MAX / 2) ++price;

		cout << price << " " << dp[price] << "\n";
	}

	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa-11517/