一个简单的动态规划题目

题目描述

假设您是个土豪，身上带了足够的 $1$ 元以及 $n$ 种奇葩面值的钞票。现在您的目标是凑出某个金额$w$，需要用到尽量少的钞票。

输入格式

程序的输入共有两行：
第一行为 $2$ 个整数 $n$ 和 $w$
第二行为 $n$ 个整数 $p_i$ 代表除了 $1$ 元以外的其他钞票面额

输出格式

一个整数，凑出目标金额使用的最少的钞票数量

样例 #1

样例输入 #1

2 15
5 11

样例输出 #1

3

样例 #2

样例输入 #2

4 99
5 7 20 50

样例输出 #2

6

说明

$1 \leq n\leq 100$
$0 \leq w\leq 10^6$

示例题解

cpp
#include <iostream>
#include <algorithm>

int main() {
#ifdef OHTOAI_LOCAL_MACHINE
    std::freopen("input.txt", "r", stdin);
#endif
    using std::cin;
    using std::cout;
    using std::endl;
    std::ios::sync_with_stdio(false);

    int f[1000001] = {0};
    int money[100];

    int n, w;
    cin >> n >> w;
    for (int i = 0; i < n; ++i) {
        cin >> money[i];
    }

    std::sort(money, money + n);
    for (int i = 0; i < n; ++i) {
        cout << money[i] << ", ";
    }
    cout << endl;

    for (int i = 2; i <= w; ++i) {
        int min_cost = f[i - 1] + 1;
        for (int c = 0; c < n && i >= money[c]; ++c) {
            auto new_cost = f[i - money[c]] + 1;
            if(min_cost > new_cost) {
                min_cost = new_cost;
            }
        }
        f[i] = min_cost;
    }
    cout << f[w] << endl;

    return 0;
}