现有面值为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

你也可能喜欢

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注