动态规划之硬币问题

灯珑LoGin

发布于 2022-10-31 13:15:59

4600

发布于 2022-10-31 13:15:59

文章被收录于专栏：龙进的专栏

现有面值为c1,c2,c3,…,cm的m种硬币，求支付n元时所需硬币的最少枚数。各面值的硬币可以使用任意次

首先最开始想到的是贪心算法，也就是从最大面值的硬币开始用。但是贪心算法只关注当前的最优解，所得结果不一定是全局最优解。

举个例子，当面值为1、2、7、8、12、50时，我们如果需要支付15元，用贪心算法来算的话，就会出现12、2、1的结果，需要三枚硬币。但是事实上，我们只需要7、8元面值的两枚硬币就够了。

所以，硬币问题可以用动态规划来求解。

用c[i]来存储硬币的面值，用T[j]来存储支付j元的时候所需的最少硬币数量。

那么，分析之后就可以得出下面的状态转移方程：

T[j] = min(T[j], T[j-c[i]]+1)

其实就是在当前情况下，将用上第i枚硬币与已有的最优解进行对比，如果用了第i枚硬币，结果更优，则更新T[j]，得到当前最优解。经过一轮计算下来，就能得出全局最优解了。

题目：DPL_1_A

AC代码：

#include <iostream>
using namespace std;

#define MAXN 50005
#define INF (1<<28)

int n, m;
int c[25] = {0};
int t[MAXN] = {0};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; ++i)
        cin >> c[i];

    for(int i=1;i<MAXN;++i)
        t[i] = INF;

    for (int j = 1; j <= n; ++j)
    {
        for (int i = 0; i < m; ++i)
            if (j - c[i] >= 0)
                t[j] = min(t[j], t[j - c[i]] + 1);
    }

    cout << t[n] << endl;
}

转载请注明出处：https://www.longjin666.top/?p=804

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021年2月17日2，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法