频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
贪心算法解硬币找零问题
2015-03-04 09:25:14         来源:我们终究不是童话。  
收藏   我要投稿

假如有一种货币,它有面值为1分、2分、5分和1角的硬币,最少需要多少个硬币来找出K分钱的零钱?

按照贪心算法的思想,需要不断地使用面值最大的硬币。如果要找零的值小于最大的硬币值,则尝试第二大的硬币,依次类推。

代码如下:

#include 
using namespace std;

#define ONE 1
#define TWO 2
#define FIVE 5
#define TEN 10

int main()
{
    int money;
    int one=0,two=0,five=0,ten=0;
    cout<<"输入要找零的钱(以分为单位):";
    cin>>money;
    
    //尝试每一种硬币
    while (money>=TEN)
    {
        ten++;
        money-=TEN;
    }
    while (money>=FIVE)
    {
        five++;
        money-=FIVE;
    }
    while (money>=TWO)
    {
        two++;
        money-=TWO;
    }
    while (money>=ONE)
    {
        one++;
        money-=ONE;
    }
    
    //输出结果
    cout<<"1角硬币数:"<
虽然贪心算法不是对所有问题都能得到整体的最优解,但是实际应用中的许多问题都可以使用贪心算法得到最优解。有时即使使用贪心算法不能得到问题的最优解,但最终结果也是较优的解

点击复制链接 与好友分享!回本站首页
相关TAG标签 硬币 算法 问题
上一篇:Java8读文件仅需一行代码
下一篇:重构笔记——移除中间人
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站