选硬币该用动态规划

选硬币：
现有面值分别为1角1分，5分，1分的硬币，请给出找1角5分钱的最佳方案。

#include 
#include 

std::vector<int> findChange(int amount) {
    std::vector<int> coins = {11, 5, 1}; // 按面值从大到小排序的硬币面值
    std::vector<int> result(coins.size(), 0); // 用于存储每种硬币的数量

    for (int i = 0; i < coins.size(); i++) {
        int numCoins = amount / coins[i]; // 计算当前硬币面值的数量
        result[i] = numCoins; // 存储数量

        amount -= numCoins * coins[i]; // 更新剩余金额
    }
    return result;
}

int main() {
    int amount = 15; // 需要找零的金额，单位为分
    std::vector<int> change = findChange(amount);

    std::cout << "找零方案为：" << std::endl;
    std::cout << "1角1分硬币数量：" << change[0] << std::endl;
    std::cout << "5分硬币数量：" << change[1] << std::endl;
    std::cout << "1分硬币数量：" << change[2] << std::endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

一开始我想的很简单，以为是简单的求整除数。
但要是你仔细一想，这肯定是不对的，不是所有问题都能用贪心。
在求最优的过程中，贪心和动态规划一直是一对冤家，到底选择哪个，难道了很多英雄好汉，所以最好的方式就是具体问题具体分析，只有结合实际情况才能选出最适合问题的算法。
我们都知道贪心的局限性，只能求出其中一个解的，但是不是最优需要考量。
让我们来看一下用上面贪心求出来的解：

但这肯定不是最优解，我们在找零的时候遵循的规则是用最少的钱张数交给别人，这样才方便。
所以最佳找零方案为：
1角1分硬币数量：0
5分硬币数量：3
1分硬币数量：0
让我们来看看用动态规划写出来的代码：

#include 
using namespace std;

const int N = 10005;
const int INF = 0x3f3f3f3f; 
int f[N], a[N];

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

    for (int i = 1; i <= w; i++) {
        f[i] = INF;
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = a[i]; j <= w; j++) {
            f[j] = min(f[j], f[j - a[i]] + 1);
        }
    }

    if (f[w] == INF) {
        cout << -1; 
    } else {
        cout << f[w];
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

结果和我们预期的完全一样

总结

选硬币在动态规划中是一种叫状态表示的题型，通常用一维/二维的数组组成状态转移方程，通过更新数组来达到获取最优解的目标