貪心算法——找紙幣問題 · 算法程序設計

貪心算法——找紙幣問題 <table border="1" style="font-family:Simsun; border-collapse:collapse; width:80%; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)">問題主題：找錢</td></tr><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,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<=1090<=K<=109</td></tr><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)">樣例：輸入C0=3,?c1=0,?c2=2,?c3=1,?c4=0,?c5=3,?c6=5輸出6</td></tr></tbody></table> ### 【解法一】 ### 解題分析： ???本題使用貪心算法，只需要考慮“盡可能多地使用面值大的紙幣”，然后根據面值的大小從大到小排序依次選擇。 ### 程序實現: **C++** <table border="1" style="font-family:Simsun; border-collapse:collapse; width:80%; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.8pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)">#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;elsecout?<<?"NO"?<<?endl;return?0;}?</td></tr></tbody></table> **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);