題目描述

某國有 $n$ 種紙幣，每種紙幣面額為 $a_i$ 并且有無限張，現在要湊出 $w$ 的金額，試問最少用多少張紙幣可以湊出來？

輸入格式

第一行兩個整數 $n,w$，分別表示紙幣的種數和要湊出的金額。
第二行一行 $n$ 個以空格隔開的整數 $a_1,a_2,a_3,\dots a_n$ 依次表示這 $n$ 種紙幣的面額。

輸出格式

一行一個整數，表示最少使用的紙幣張數。

輸入輸出樣例 #1

輸入 #1

6 15
1 5 10 20 50 100

輸出 #1

2

輸入輸出樣例 #2

輸入 #2

3 15
1 5 11

輸出 #2

3

說明/提示

對于 $40\%$ 的數據，滿足 $n\le 10$，$w\le 100$；
對于 $100\%$ 的數據，滿足 $1\le n\le 10^3$，$1\le a_i,w\le 10^4$。

solution

動態規劃：

• 1 定義公式：
  • 設 f[i][j]: 如果只用前 i 種紙幣，最少需要多少張才能拼成 j 元。
• 2 遞推關系：
  • f[i][j] = min(f[i][j], f[i][j - a[i]] + 1, f[i-1][j])
  • 因為 i 只影響 i + 1，所以只需要保存一個，可以省略一個維度
    遞推公式 f[j] = min(f[j], f[j - a[i]] + 1)
• 3 結果
  f[w]

代碼

#include<iostream>
#include "unordered_map"
#include "unordered_set"
#include "stack"
#include "queue"
#include "cstring"
#include "algorithm"using namespace std;
const int N = 1e3 + 5, INF = 1e4, M = 1e4 + 5;int a[N], n, w, f[M];int main() {cin >> n >> w;for (int i = 0; i < n; i++) cin >> a[i];for (int j = 1; j <= w; j++) {f[j] = INF;for (int i = 0; i < n; i++) {if (j >= a[i]) {f[j] = min(f[j], f[j - a[i]] + 1);}}}cout << f[w];return 0;
}

結果