贪心算法

左手的ㄟ右手 2022-09-26 03:58 213阅读 0赞

# 找零钱问题 #

the problem of “Making Change”.

Coins available are:

dollars (100 cents)  
quarters (25 cents)  
dimes (10 cents)  
nickels (5 cents)  
pennies (1 cent)

problem： Making a change of a given amount using the smallest possible number of coins.

#include <iostream>
    #include <array>
    #include <vector>
    using namespace std;
    
    int main() {
        // your code goes here
        array<int, 5> coins = {
       100, 25, 10, 5, 1};
        int n;
        cin >> n;
        int sum = 0;
        vector<int> changes;
        for (int i = 0; i < coins.size();) {
            if (sum + coins[i] <= n) {
                sum += coins[i];
                changes.push_back(coins[i]);
                i = 0;
            } else {
                i++;
            }
        }
        int i = 0;
        while (sum != n) {
            if (sum + coins[i] <= n) {
                sum += coins[i];
                changes.push_back(coins[i]);
                i = 0;
            } else {
                i++;
            }
        }
        cout << "need smallest " << changes.size() << " coins: ";
        for (auto c : changes) {
            cout << c << " ";
        }
        cout << endl;
        return 0;
    }

# 贪心算法的可行性定义 #

使用贪心算法求得的解不仅是问题解集合中的一种解，也是该问题的最优解。

解决动态规划问题由底向上，而贪心法通常由顶向下，且每一个问题都做出最贪心的选择，并逐步减小每一个问题到更小规模。

# 参考 #

[Greedy Introduction][]

[Greedy Introduction]: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/greedyIntro.htm

发表评论取消回复

表情：

评论列表（有 0 条评论，213人围观）

还没有评论，来说两句吧...

相关阅读

相关贪心算法

贪心算法也称贪婪算法，其核心思想就是：每步都采用最优的做法。贪心算法所得到的结果往往不是最优的结果(有时候是最优解)，但都是相对接近最优解的。

客官°小女子只卖身不卖艺/ 2023年01月14日 01:49/ 0 赞/ 131 阅读

相关贪心算法

一：贪心算法介绍 1. 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。 2.

青旅半醒/ 2022年11月13日 05:29/ 0 赞/ 182 阅读

相关贪心算法

找零钱问题 the problem of “Making Change”. Coins available are: dollars (100 cents) qu

左手的ㄟ右手/ 2022年09月26日 03:58/ 0 赞/ 214 阅读

相关贪心算法

贪心算法的基本要素对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题

素颜马尾好姑娘i/ 2022年07月12日 15:22/ 0 赞/ 332 阅读

相关贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。举一个简单的贪心法例子，平时

本是古典何须时尚/ 2022年06月06日 03:11/ 0 赞/ 280 阅读

相关贪心算法

1.钞票支付问题，1元，2元，5元，10元，20元，50元，100元钞票无穷张，使用这些钞票怎么支付，最少需要多少张。思路：尽可能使用面额较大的金额数目。反证法：若不成立，

深碍√TFBOYSˉ_/ 2022年02月22日 08:49/ 0 赞/ 282 阅读

相关贪心算法

一、什么是贪心算法贪心算法，又称贪婪算法(Greedy Algorithm)，是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优解出发来考虑，它

ゞ浴缸里的玫瑰/ 2022年01月29日 05:39/ 0 赞/ 329 阅读

相关贪心算法

贪心算法概念设计贪心算法的步骤案例剪绳子问题描述解决思路代码实

我就是我/ 2021年11月04日 13:48/ 0 赞/ 433 阅读

相关贪心算法

一问题提出集合覆盖问题假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。如何选择最少的广播台，让所有的地区都可以接收到信号。 ![watermark

待我称王封你为后i/ 2021年07月24日 22:30/ 0 赞/ 470 阅读

相关贪心算法

[https://www.cnblogs.com/xsyfl/p/6938642.html][https_www.cnblogs.com_xsyfl_p_6938642.htm

梦里梦外;/ 2021年06月11日 15:14/ 0 赞/ 556 阅读