貪心算法
選擇目前最優(yōu)策略，不考慮全局最優(yōu)
三步走
第一步
明確最優(yōu)解
第二步
明確子問題的最優(yōu)解
第三步
分別求出子問題的最優(yōu)解再堆疊出全局最優(yōu)解
例子
背包問題
有一個(gè)背包，最多能承載150斤的重量升敲，現(xiàn)在有7個(gè)物品，重量分別為[35, 30, 60, 50, 40, 10, 25]浇坐，它們的價(jià)值分別為[10, 40, 30, 50, 35, 40, 30]魄梯，如何使背包背走最多價(jià)值的物品
方法一：
1.在重量限制范圍內(nèi)，價(jià)值最大的選擇是最優(yōu)解
2.每次盡量選擇當(dāng)前價(jià)值最高的物品兄墅，稱為“局部最優(yōu)解”
3.選擇4 2 6 5；總重量130晃酒；總價(jià)值165表牢；
方法二
1.質(zhì)量最輕為最優(yōu)解
2.選擇6 7 2 1 5；總重量：140贝次；總價(jià)值：155崔兴；
方法一比較好
核心問題
一、為何求局部最優(yōu)解
1.原問題復(fù)雜度過高
2.求全局最優(yōu)解的數(shù)學(xué)模型難以建立蛔翅；
3.求全局最優(yōu)解的計(jì)算量過大
4.沒有太大必要一定要求出全局最優(yōu)解敲茄，“比較優(yōu)即可”
二、如何分解為子問題
按串行任務(wù)分
時(shí)間串行的任務(wù)山析，按子任務(wù)來分解堰燎，即每一步都是在前一步的基礎(chǔ)上再選擇當(dāng)前的最優(yōu)解。
按規(guī)模遞減分
規(guī)模較大的復(fù)雜問題笋轨，可以借助遞歸思想秆剪，分解成一個(gè)規(guī)模小一點(diǎn)點(diǎn)的問題，循環(huán)解決爵政，當(dāng)最后一步的求解完成后就得到了所謂的“全局最優(yōu)解”仅讽。
按并行任務(wù)分
這種問題的任務(wù)不分先后，可能是并行的茂卦，可以分別求解后何什，再按一定的規(guī)則（比如某種配比公式）將其組合后得到最終解组哩。
三等龙、如何判段貪心算法的結(jié)果逼近了全局最優(yōu)值
邏輯分析上不會(huì)超過忍受范圍即可
