文档章节

贪心算法——找纸币问题

自由的角马
 自由的角马
发布于 2015/01/10 13:56
字数 515
阅读 79
收藏 0

贪心算法——找纸币问题

 

问题主题:找钱

问题描述:

假设有1元、2元、5元、10元、20元、50元、100的纸币分别为c0, c1, c2, c3, c4, c5, c6,张。现在要用这些钱来支付K元,至少要用多少张纸币?如果能找,则输出纸币的张数,不能找则输出No

限制条件:

0<=c0, c1,c2,c3,c4,c5,c6<=109

0<=K<=109

样例:

输入

C0=3, c1=0, c2=2, c3=1, c4=0, c5=3, c6=5

输出

6

 

 

【解法一】

解题分析:

    本题使用贪心算法,只需要考虑“尽可能多地使用面值大的纸币”,然后根据面值的大小从大到小排序依次选择。

程序实现:

 

C++

#include "iostream"

 

using namespace std;

 

const int N = 7;

static int K = 6200;

int min(int num1, int num2);

 

int momeyCount[N] = {3, 0, 2, 1, 0, 3, 5};

int value[N] = {1, 2, 5, 10, 20, 50, 100};

 

 

int giveChange() {

int num = 0;

for(int i = N-1; i >= 0; i --) {

int c = min(K/value[i], momeyCount[i]);

K = K - c * value[i];

num += c;

}

if(K > 0) 

num = -1;

return num;

}

 

int min(int num1, int num2) {

return num1 < num2 ? num1 : num2;

}

 

int main() {

int result = giveChange();

if(result != -1)

cout << result << endl;

else

cout << "NO" << endl;

return 0;

}

 

Java

package greed;

import java.util.Arrays;

/**
 * 找钱问题
 * User: luoweifu
 * Date: 14-1-14
 * Time: 下午8:08
 */
public class GiveChange {
	public static int gaiveChange(MoneyBox[] moneyBoxes, int target) {
		Arrays.sort(moneyBoxes);
		int count = 0;
		for(int i = moneyBoxes.length-1; i >= 0; i--) {
			int currentCount = Math.min(moneyBoxes[i].getCount(), target/moneyBoxes[i].getValue());
			target -= currentCount*moneyBoxes[i].getValue();
			count += currentCount;
		}
		if(target > 0) {
			count = -1;
		}
		return count;
	}

	public static void main(String args[]) {
		MoneyBox[] moneyBoxes = {
			new MoneyBox(1, 3),
			new MoneyBox(2, 0),
			new MoneyBox(5, 2),
			new MoneyBox(10, 1),
			new MoneyBox(20, 0),
			new MoneyBox(50, 3),
			new MoneyBox(100, 5),
		};
		int result = gaiveChange(moneyBoxes, 620);
		if(result > 0)
			System.out.println(result);
		else
			System.out.println("No");
	}
}

/**
 * 钱盒子
 */
class MoneyBox implements Comparable{
	private int value;
	private int count;

	MoneyBox(int value, int count) {
		this.value = value;
		this.count = count;
	}

	int getValue() {
		return value;
	}

	void setValue(int value) {
		this.value = value;
	}

	int getCount() {
		return count;
	}

	void setCount(int count) {
		this.count = count;
	}

	@Override
	public int compareTo(Object o) {
		MoneyBox moneyBox = (MoneyBox)o;
		if(this.value < moneyBox.getValue())
			return -1;
		else if(this.value == moneyBox.getValue())
			return 0;
		else
			return 1;
	}
}

 

算法复杂度:

    时间复杂度:如果纸币已经排序(如C++代码),O(n);如果纸币未经排序 (如Java代码),O(nlogn);

本文转载自:http://blog.csdn.net/luoweifu/article/details/18190575

下一篇:
自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
钱币找零问题---贪心算法入门例题

笔者近期无意中发现了一篇关于贪心算法的博客,写的真好。作为一名算法萌新,感觉这篇文章来入门真心不错,于是摘记其中一个典型的关于贪心算法的例题。博客传送门:从零开始学贪心算法 钱币...

孤独的岛_Bin
2018/03/09
564
0
零基础学贪心算法

本文在写作过程中参考了大量资料,不能一一列举,还请见谅。 贪心算法的定义: 贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,只做出在某...

angel_kitty
2017/02/24
0
0
动态规划之硬币表示问题

问题描述: 有数量不限的硬币,币值为25分、10分、5分和1分,请编写代码计算n分有几种表示法。 求解思路: 这也是典型的动态规划问题,我们可以这样考虑:当只有1分的硬币时,n从1到n分别有多...

一贱书生
2016/11/22
76
0
“365算法每日学计划”:03打卡-贪心算法

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。 “计划”的主要目的: 1、想通过这样...

wx好好学java
2018/06/16
0
0
优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆
2011/12/03
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

采坑指南——k8s域名解析coredns问题排查过程

正文 前几天,在ucloud上搭建的k8s集群(搭建教程后续会发出)。今天发现域名解析不了。 组件版本:k8s 1.15.0,coredns:1.3.1 过程是这样的: 首先用以下yaml文件创建了一个nginx服务 apiV...

码农实战
2分钟前
1
0
【2019年8月版本】OCP 071认证考试最新版本的考试原题-第6题

choose three Which three statements are true about indexes and their administration in an Orade database? A) An INVISIBLE index is not maintained when Data Manipulation Language......

oschina_5359
5分钟前
1
0
阿里巴巴开源 Dragonwell JDK 最新版本 8.1.1-GA 发布

导读:新版本主要有三大变化:同步了 OpenJDK 上游社区 jdk8u222-ga 的最新更新;带来了正式的 feature:G1ElasticHeap;发布了用户期待的 Windows 实验版本 Experimental Windows version。...

阿里巴巴云原生
10分钟前
1
0
教你玩转Linux—磁盘管理

Linux磁盘管理好坏直接关系到整个系统的性能问题,Linux磁盘管理常用三个命令为df、du和fdisk。 df df命令参数功能:检查文件系统的磁盘空间占用情况。可以利用该命令来获取硬盘被占用了多少...

xiangyunyan
13分钟前
3
0
js 让textarea的高度自适应父元素的高度

textarea按照普通元素设置height是没有作用的,可以这么来设置, 下面给上一段项目代码 JS代码: $.fn.extend({ txtaAutoHeight: function () { return this.each(function () {...

文文1
14分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部