d904: 換零錢

解題心得

price放幣值種類，大小順序不重要。

每次單看一種種類的幣值，把1~c的目標金額都算過一次，如果新的(也就是扣掉自己的那個金額再加一)比現在需要的硬幣少，就更新。

參考這個跟這個網站。

程式碼

#include <iostream>
using namespace std;

int price[11] = { 0 }, money[1001] = { 0 };

int main()
{
	int c, n;
	while (cin >> c >> n)
	{
		for (int i = 0; i < n; i++)
			cin >> price[i];
		for (int i = 1; i < 1001; i++)
			money[i] = 1000000;
		for (int i = 0; i < n; i++)
		{
			for (int j = price[i]; j <= c; j++)
			{
				money[j] = min(money[j], money[j - price[i]] + 1);
			}
		}
		if (money[c] != 1000000) cout << money[c] << endl;
	}
	return 0;
}