2019独角兽企业重金招聘Python工程师标准>>> 
贪心算法——找纸币问题
| 问题主题：找钱 |
| 问题描述： 假设有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);elseSystem.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;}@Overridepublic int compareTo(Object o) {MoneyBox moneyBox = (MoneyBox)o;if(this.value < moneyBox.getValue())return -1;else if(this.value == moneyBox.getValue())return 0;elsereturn 1;}
}
|
算法复杂度：
时间复杂度:如果纸币已经排序(如C++代码)，O(n);如果纸币未经排序 (如Java代码)，O(nlogn);
