題意#
給定一個目標金額 \( x \) 以及 \( n \) 種不同面額的硬幣。
每種面額的硬幣數量都是無限的，你可以無限次使用。你的任務是找出：要湊出精準等於 \( x \) 的金額，最少需要多少枚硬幣？
如果根本湊不出這個金額，則輸出 -1。
思路#
這是一題標準的「完全背包問題」，也就是所謂的零錢兌換問題。
我們可以使用動態規劃來解。定義一個長度為 \( x + 1 \) 的陣列 dp，其中 dp[j] 代表「湊出金額 \( j \) 所需要的最少硬幣數量」。
由於我們要找的是最小值，一開始最好把 dp 陣列的所有元素都設為一個極大的值（代表目前還不知道怎麼湊出這個金額），只有 dp[0] 設為 0（湊出 0 元需要 0 枚硬幣）。
接著我們輪流考量每種面額的硬幣（假設面額為 v[i]）。對於任意能夠容納這枚硬幣的金額 j（也就是 j >= v[i]），我們可以選擇「不使用這枚硬幣（維持原本的 dp[j]）」，或是「使用一枚這面額的硬幣（這會讓金額變成 j - v[i]，所以需要的硬幣數就是 dp[j - v[i]] + 1）」。我們取兩者之中比較小的那個值來更新 dp[j]。
跟 0/1 背包問題不同的是，因為硬幣數量是無限的，所以內部的迴圈可以直接從小金額往大金額遍歷，這樣就可以允許同一面額的硬幣被重複選取。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n, x; cin >> n >> x;
// 初始化 dp 陣列，預設為無限大 (INF)
// dp[0] = 0 代表湊出 0 元需要 0 枚硬幣
vector<int> v(n), dp(x+1, INF); dp[0] = 0;
// 讀取所有硬幣的面額
for (auto &i : v) cin >> i;
for (int i = 0; i < n; i++) {
// 從當前面額 v[i] 開始，正序走到目標金額 x
// 正序遍歷允許同一種硬幣被選擇多次
for (int j = v[i]; j <= x; j++) {
// 取不使用該硬幣 (dp[j]) 與使用一枚該硬幣 (dp[j-v[i]] + 1) 的最小值
dp[j] = min(dp[j], dp[j-v[i]]+1);
}
}
// 如果 dp[x] 依然是 INF，代表無法用這些硬幣湊出目標金額
if (dp[x] == INF) cout << "-1\n";
else cout << dp[x] << '\n';
}
