贪心法的求解步骤
在分析和求解某个问题时，在每一步的计算选择上都是最优的或者最好的，通过这种方式期望最终的计算的结果也是最优的。也就是说，算法通过先追求局部的最优解，从而寻求整体的最优解。
贪心算法的基本步骤：
1、首先定义问题，确定问题模型是不是适合使用贪心算法，即求解最值问题；
2、将求极值的问题进行拆解，然后对拆解后的每一个子问题进行求解，试图获得当前子问题的局部最优解；
3、所有子问题的局部最优解求解完成后，把这些局部最优解进行汇总合并，得到最终全局的最优解，那么这个最优解就是整个问题的最优解。
通过场景理解算法
概念性的算法描述可能大家都不太好理解，所以需要结合一些实际的场景来进行说明。这里以我们小时候的找零钱的例子来进行切入。虽然现在大家都用手机扫一扫进行支付，已经很久到没碰过钱了，但是并不妨碍找零问题 可帮助我们形象的理解贪心算法的实现过程。
假设你是一家小卖店的老板，你有各种面值大小的零钱，如1块钱、3块钱、5块钱。这个时候有个小朋友过来买东西，他要求你找的零钱要张数最小，这样他的口袋才能装得下。假设我们分别把零钱记为c[0]、c[1]、c[2] …，小朋友拿来买零食的钱我们记为total。那么刚才说的小朋友希望获得最少张数零钱的需求我们就可以把他转化为一个编程求最优解的问题，即给定总数total，求解最少需要几个c相加的和等于给定的总数total。
例子1：
假设给定需要找的零钱为11，当前的零钱为1块、3块、5块。
输入：total=11，c[0]=1,c[1]=3,c[2]=5
输出：3
问题分析
通过提取问题中的关键词“最少”，我们可以明确此问题的实际上就是一个求解最值的问题，只要找到满足条件的最小零钱张数就可以解决找回最少零钱的问题了。想要找到最小的零钱张数，我们最先想到的方法就是进行穷举，列举出来所有可能的满足总数为11的零钱组合。如下图所示，再在这些组合中找到使用零钱张数最少的组合再计算具体的张数，我们就可以获得最终的答案了。但是这显然不是一个好的解决思路。因为如果对应的total很大，我们穷举的结果将会爆发性增长。
那有没有更好的解决办法呢？这时候我们就可以考虑下贪心算法的实现了，找到满足要求的最小张数零钱。既然是找零钱，那么我们可以将问题转换为找到满足总数total的零钱最少需要几个步骤，实际上就是将问题拆分到每次找零钱的小步骤中，而贪心算法的核心就是需要在每个小步骤中贪心寻求局部最优解。因此在找零钱的每个步骤中，都需要找到该步骤中对应的最优解零钱大小，接下来我们来一起看下贪心算法执行过程。这里假设各个面值的零钱比较充足。
在寻找零钱的步骤中，首先获取最大面值为5的零钱（贪心，上来就找最大的），接着发现剩余待找零钱6=11-5，于是继续寻找最大的面值为5的零钱（继续贪心），待找零钱1=6-5。此时只要获取面值为1的零钱就可以完成任务了，再将之前步骤中的结果整合到一起，最终我们得出想要获取total为11的最少张数零钱的大小为3。通过这样的分析，贪心算法是不是也没有那么的复杂。
/**
* @Author: mufeng
* @Date: 2022/5/15 15:33
* @Version: V 1.0.0
* @Description: 计算最小满足条件的零钱张数
*/public class MinChangeCountSolution {
public static void main(String[] args) {
int values[] = {5,5,3,3,1};
System.out.println(getMinChangeCount(11, values));
}
//假设values数组从大到小排列
static int getMinChangeCount(int total, int[] values) {
int rest = total;
int result = 0;
int count = values.length;
// 从大到小遍历所有面值
for (int i = 0; i < count; ++ i) {
//计算需要几张这种面值的零钱
int needCount = rest / values[i];
//计算使用后的余额
rest -= needCount * values[i];
//计数增加
result += needCount;
if (rest == 0) {
return result;
}
}
//没有找到合适的面值
return -1;
}}123456789101112131415161718192021222324252627282930313233123456789101112131415161718192021222324252627282930313233
以上我们分析了贪心算法的大致实现过程，但是实际上还是有问题的。不知道大家有没有发现，由于贪心算法过于贪心，每一个步骤都想要找到局部最优解。那么假如在上面的例子中，我们没有1块钱的零钱，上述代码的返回结果是-1，即没有符合条件的答案。但是实际并非如此，也就是说5,3,3也是满足条件的，但是上述代码却没有找到。
所以上述代码还是有问题的，关键点就在于，当发现没有1元零钱的时候，需要回头去看能不能把第二步骤中的5元零钱换成3元零钱再进行后续的迭代，如果有这样的步骤，那么就可以找到5,3,3这样的组合。
总结
本文主要通过对于贪心算法的描述，并结合实际的找零钱的例子，带大家一起分析了贪心算法的具体实现过程。同时分析了贪心算法存在的不足，即容易陷入局部最优的陷阱无法自拔，导致最终无法给出满足条件的结果，这也是大家以后在使用贪心算法分析问题时特别需要注意的问题。
起分析了贪心算法的具体实现过程。同时分析了贪心算法存在的不足，即容易陷入局部最优的陷阱无法自拔，导致最终无法给出满足条件的结果，这也是大家以后在使用贪心算法分析问题时特别需要注意的问题。
绛旓細璐┆绠楁硶(Greedy Algorithm)涔熷彨绠璐績娉,璐┆娉.瀹冩槸涓涓伒寰惎鍙戝紡瑙ｅ喅闂鐨勭畻娉曡寖寮.瀹冪殑鏍稿績鎬濇兂灏辨槸閫氳繃鍦ㄦ瘡涓姝ョ殑閫夋嫨涓兘閫夌敤褰撳墠姝ラ涓嬫渶浼樼殑閫夋嫨,鏈熸湜缁撴灉鏄渶浼樼殑绠楁硶.濡 鏃呰鎺ㄩ攢鍛橀棶棰 .璐┆绠楁硶灏ゅ叾閫傜敤浜庢湁鏈浼樺瓙缁撴瀯鐨勯棶棰樹腑,鏈浼樺瓙缁撴瀯鐨勬剰鎬濇槸灞閮ㄧ殑鏈浼樿В鍙互瀵煎嚭鍏ㄥ眬鐨勬渶浼樿В....
绛旓細1. 璐績娉曪紙Greedy Algorithm锛夊畾涔 姹傝В鏈浼樺寲闂鐨勭畻娉曢氬父闇瑕佺粡杩囦竴绯诲垪鐨姝ラ锛屽湪姣忎釜姝ラ閮介潰涓村绉嶉夋嫨锛涜椽蹇冩硶灏辨槸杩欐牱鐨勭畻娉曪細瀹冨湪姣忎釜鍐崇瓥鐐逛綔鍑哄湪褰撴椂鐪嬫潵鏈浣崇殑閫夋嫨锛屽嵆鎬绘槸閬靛惊鏌愮瑙勫垯锛屽仛鍑哄眬閮ㄦ渶浼樼殑閫夋嫨锛屼互鎺ㄥ鍑哄叏灞鏈浼樿В锛堝眬閮ㄦ渶浼樿В->鍏ㄥ眬鏈浼樿В锛2. 瀵璐績娉曠殑娣卞叆鐞嗚В 锛1...
绛旓細璐績绠楁硶瑙ｅ喅鑳屽寘闂鏈夊嚑绉嶇瓥鐣ワ細(i)涓绉嶈椽濠噯鍒欎负锛氫粠鍓╀綑鐨勭墿鍝佷腑锛岄夊嚭鍙互瑁呭叆鑳屽寘鐨勪环鍊兼渶澶х殑鐗╁搧锛屽埄鐢ㄨ繖绉嶈鍒欙紝浠峰兼渶澶х殑鐗╁搧棣栧厛琚鍏ワ紙鍋囪鏈夎冻澶熷閲忥級锛岀劧鍚庢槸涓嬩竴涓环鍊兼渶澶х殑鐗╁搧锛屽姝ょ户缁笅鍘汇傝繖绉嶇瓥鐣ヤ笉鑳戒繚璇佸緱鍒版渶浼樿В銆備緥濡傦紝鑰冭檻n=2, w=[100,10,10], p =[20,15,15...
绛旓細杩囩▼涓紝闅嗗熀寰楁倝骞村辜鏃堕伃鍔涘＋瀚佺ジ锛岃岃褰撲紬鑴辫￥鐨勫師鐢憋紝姘旀瀬锛涘張瑙佸埌濠村鏃惰瀹コ閬楀純浜庡北涓殑缁忚繃锛屽彲鎯滃綋浠栧揩鍙湪鐙变腑瑙佸埌濞樹翰鏃讹紝鍗村洜纰х懚鏁板害鏂芥硶锛屽厓姘斿ぇ浼わ紝鑰屼笌闄堝悗缂樻偔涓闈傛厱瀹归洩搴斿姏澹個璇烽儕娓革紝鍏舵椂鏈変汉閬囨汉锛屾厱瀹归洩鍥犺屽彂鐜板綋鏃ヨ惤娌虫晳鑷繁鐨勪笉鏄姏澹傛厱瀹归洩璇曟帰闅嗗熀锛屾璧忎粬鏁戜汉鑰屼笉...
绛旓細姣斿棣栧厛鎸夌墿鍝佺殑閲嶉噺浠庡皬鍒板ぇ鎺掑簭銆璐績閫夋嫨鎬ц川璇寸殑灏辨槸姣忔閮芥槸閮芥槸閫夊彇褰撳墠鐨勬渶浼樺笺傚亣璁捐儗鍖呴棶棰樻瘡娆￠兘鏄粠閲嶉噺鏈灏忕殑鐗╁搧寮濮嬮夋嫨鐨勶紝閭ｄ粬涓瀹氭弧瓒宠椽蹇冮夋嫨鎬ц川锛屽亣璁捐儗鍖呴棶棰樹笉鏄粠閲嶉噺鏈灏忕殑鐗╁搧寮濮嬮夋嫨鐨勶紝閭ｄ箞璇存槑閲嶉噺鏈灏忕殑鐗╁搧娌℃湁瑁呭叆锛岀幇鍦ㄦ垜浠敤杩欎釜閲嶉噺鏈灏忕殑鐗╁搧浠ｆ浛褰撳墠閫夋嫨瑁呭叆鐨勭墿鍝...
绛旓細2銆佸垎鏀畾鐣屾硶锛氬垎鏀畾鐣屾硶鏄竴绉嶈繎浼肩畻娉,瀹冭瘯鍥惧湪鏈夐檺鐨勬椂闂村唴鎵惧埌鏈浼樿В銆傚畠浠庢悳绱㈡爲鐨勬牴缁撶偣寮濮,骞朵笖姣忔鍙冭檻涓涓瓙缁撶偣銆3銆璐績绠楁硶锛氳椽蹇冪畻娉曟槸涓绉嶈繎浼肩畻娉,瀹冭瘯鍥惧湪姣忎竴姝ラ夋嫨鏈浼樿В,浠庤屽鑷存渶缁堢殑鏈浼樿В銆傚洖婧硶锛1锛夛紙姹傝В鐩爣锛夊洖婧娉曠殑姹傝В鐩爣鏄壘鍑鸿В绌洪棿涓弧瓒崇害鏉熸潯浠剁殑涓涓...
绛旓細2.閫掑綊鍥炴函娉曪細閫氳繃閫掑綊鍦板皾璇曚负姣忎釜椤剁偣鍒嗛厤棰滆壊锛屽苟鍥炴函鎾ら攢涓嶅悎閫傜殑棰滆壊鍒嗛厤锛岀洿鍒版壘鍒版弧瓒虫潯浠剁殑鐫鑹叉柟妗堛傝繖绉嶆柟娉曢渶瑕佽璁″悎閫傜殑鍥炴函绛栫暐鍜屽壀鏋濇潯浠讹紝浠ュ噺灏戞悳绱㈢┖闂村拰鎻愰珮姹傝В鏁堢巼銆3.璐績绠楁硶锛氭牴鎹浘鐨勭粨鏋勭壒鐐癸紝閲囩敤璐績鐨勭瓥鐣ラ愭涓洪《鐐瑰垎閰嶉鑹层備緥濡傦紝鍙互鎸夌収椤剁偣鐨勫害鏁版垨鍏ュ害/鍑哄害鐨勬瘮鍊肩瓑鎸囨爣...
绛旓細銆愮瓟妗堛戯細璐績绠楁硶鐨鍩烘湰鎬濊矾锛氫粠闂鐨勬煇涓涓垵濮嬭В鍑哄彂閫愭閫艰繎缁欏畾鐨勭洰鏍囷紝浠ュ敖鍙兘蹇殑鍦版眰寰楁洿濂界殑瑙ｃ傚綋杈惧埌鏌愮畻娉曚腑鐨勬煇涓姝ヤ笉鑳藉啀缁х画鍓嶈繘鏃讹紝绠楁硶鍋滄銆
绛旓細璐┆娉鏄竴绉嶄笉杩芥眰鏈浼樿В锛屽彧甯屾湜寰楀埌杈冧负婊℃剰瑙ｇ殑鏂规硶銆傝椽濠硶涓鑸彲浠ュ揩閫熷緱鍒版弧鎰忕殑瑙ｏ紝鍥犱负瀹冪渷鍘讳簡涓烘壘鏈浼樿В瑕佺┓灏芥墍鏈夊彲鑳借屽繀椤昏楄垂鐨勫ぇ閲忔椂闂淬傝椽濠硶甯镐互褰撳墠鎯呭喌涓哄熀纭浣滄渶浼橀夋嫨锛岃屼笉鑰冭檻鍚勭鍙兘鐨勬暣浣撴儏鍐碉紝鎵浠ヨ椽濠硶涓嶈鍥炴函銆傝椽濠畻娉曠殑涓鑸柟娉 1銆侀棶棰樻弿杩 瀹冩湁n涓緭鍏ワ紝鑰屽畠鐨勮В...
绛旓細1.缁欏畾涓缁勬暟瀛楋紝姹傛渶澶у兼垨鏈灏忓 鍦ㄨ繖绉嶆儏鍐典笅锛岄渶瑕佸缁欏畾鐨勪竴缁勬暟瀛楄繘琛屾瘮杈冿紝鎵惧埌鍏朵腑鐨勬渶澶у兼垨鏈灏忓笺傚彲浠ヤ娇鐢ㄨ凯浠ｆ硶锛岄愪釜姣旇緝鏁板瓧澶у皬锛岃褰曞綋鍓嶇殑鏈澶у兼垨鏈灏忓笺2.姣旇緝澶氫釜鍥犵礌锛屾眰鏈浼樿В 褰撻渶瑕佺患鍚堝涓洜绱犳潵姹傝В鏈鍊奸棶棰樻椂锛岄渶瑕佸姣忎釜鍥犵礌杩涜鏉冭 鍜屾瘮杈冦傚彲浠ュ皢姣忎釜鍥犵礌杩涜閲忓寲锛...
