【題解】Zerojudge d904 - 換零錢

題目連結

題目大意

給定一些硬幣的幣值，問湊出 $n$ 元最少需要幾個硬幣？

題解

本題是經典的無限背包問題，我們定義 $dp[i]$ 為最少用多少硬幣湊出 $i$ 元。對於各種硬幣的幣值 $a_j$，可以得到 $dp$ 的轉移式 $dp[i] = min(dp[i], dp[i - a_j] + 1)$，代表我們不兌換幣值為 $a_j$ 的硬幣，或是湊出 $i - a_j$ 元後再去兌換 $a_j$ 元得到 $i$ 元的最少硬幣數量。最後的答案就是 $dp[n]$。其他實作的細節請參考 code。

#include <bits/stdc++.h>
using namespace std;

const int INF = 1E9;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int> dp(n + 1, INF);
	dp[0] = 0;
	for(int i = 0; i < m; i++) {
		int x;
		cin >> x;
		for(int i = x; i <= n; i++) {
			dp[i] = min(dp[i], dp[i - x] + 1);
		}
	}
	cout << dp[n] << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge d904 - 換零錢