# 題目: UVa 11517 - Exact Change

# 題目說明

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

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

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

此題為 Coin Change 問題

以一個 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/