?2016-2026 Matools All rights reserved,
粵ICP備17059708號
貪心算法顧名思義在一個(gè)貪字上面，它在解決某個(gè)問題的時(shí)候，總是先從眼前利益出發(fā)。也就是說只顧眼前，不顧大局，所以它是局部最優(yōu)解。它的核心的就是局部最優(yōu)推出全局最優(yōu)。
?
比如公司只有一個(gè)會議室，明天有幾場同樣的重要的會議要開，怎么安排會議才能盡可能的多開會。
如果我們將所有會議的結(jié)束時(shí)間從小到大排序。然后從結(jié)束時(shí)間最小的開始選（局部最優(yōu)），然后按照這個(gè)排序去遍歷判斷后面是開始時(shí)間是否在這之后，如果在則選它，如果不在，則判斷下一個(gè)是否在。這樣是否就能達(dá)到最終的最優(yōu)解？可以嘗試舉反例來證明它結(jié)果的合法性。你會發(fā)現(xiàn)在這個(gè)場景中，似乎找不到比上述方案的更好的結(jié)果了。其實(shí)這就是一個(gè)貪心算法
貪心算法：
一定會有一個(gè)排序，這個(gè)就是我們所說的貪心策略，上面問題的策略就是以會議結(jié)束時(shí)間排序；不同的貪心策略出來結(jié)果是不一樣，如果結(jié)果能被其他舉例推翻，那就說明這個(gè)策略不合理。
貪心算法不是對所有問題都能得到整體最優(yōu)解。但是如果經(jīng)過大量證明成立之后，那么它就是一種高效的算法。
?
背包問題：
小偷去偷東西，背包只有5KG容量，現(xiàn)在有三個(gè)物品（不能分割，且各自只有一個(gè)），問小偷怎么拿才能帶走最大價(jià)值的東西
A物品：1kg ?6元
B物品：2kg ?10元
C物品：4kg ?12元
如果用貪心來看，這個(gè)問題我們似乎只能根據(jù)單價(jià)來排序了A單價(jià)6，B單價(jià)5，C單價(jià)3，那么我們按排序結(jié)果選擇，就會選擇AB，這個(gè)時(shí)候我們的價(jià)值是16，顯然選擇AC
，價(jià)值是18，所以這個(gè)貪心策略很容易就被推翻了。
如此看來這個(gè)問題用貪心算法好像是無法解決了。
1.我們可以枚舉（把所有情況的列出來）來看，那用到排列組合了，C33全部列出來看，數(shù)據(jù)小還可以，數(shù)據(jù)大了呢？
2.遍歷所有，我們每個(gè)物品都有兩個(gè)操作，選或者不選。
?
?
?顯然標(biāo)紅的那條路線就是我們最優(yōu)的方案。每次在物品加進(jìn)來的時(shí)候都會保存選擇與不選擇兩種狀態(tài)那么這樣下去越到后面狀態(tài)保存的就越多其實(shí)就是2^n次。
?
3.動態(tài)規(guī)劃
問將背包按1kg來邏輯分割，可以整理出來如下表格
?
?
1kg
2kg
3kg
4kg
5kg
加入物品A
6
6
6
6
6
加入物品B
6
10
10+6=16
16
16
加入物品C
6
10
16
16
12+6=18
?
首先這個(gè)表格是從上往下一行一行的來看，前面的會影響后面的。第一行為什么全是6，因?yàn)檫@個(gè)是后只有A加入，第二行加入B，這個(gè)時(shí)候前面有一行A
的數(shù)據(jù)了，所以要一起考慮A了.....
從第二行開始看下具體的邏輯，加入物品B，當(dāng)背包容量1kg的時(shí)候，B是裝不進(jìn)去的，但是前面的數(shù)據(jù)1kg的時(shí)候可以裝A，所以價(jià)值是6；背包容量2kg
這個(gè)時(shí)候剛好可以裝B，比較下B和之前的價(jià)值，發(fā)現(xiàn)10是大于6的，顯然我們裝B；背包容量3kg的時(shí)候，顯然裝完B，還剩1kg，因此可以一起裝就是價(jià)值16
第三行的1 2 3列數(shù)據(jù)同理，C裝不下但是可以裝A和B；當(dāng)背包4kg時(shí)，可以裝下C，但是C的價(jià)值才12，而且裝完C之后沒有容量了，然而我們不裝C的時(shí)候
價(jià)值都是16了，顯然我們不裝C；當(dāng)背包5kg的時(shí)候，這個(gè)時(shí)候可以裝C，價(jià)值12，裝完還剩1kg，前面1kg的時(shí)候可以裝A，因此12+6=18的價(jià)值。
這個(gè)表格最后的數(shù)據(jù)就是我們所需要的最優(yōu)結(jié)果。
能裝的時(shí)候 每次和上面的比較，大我就裝，否則就不裝。這個(gè)過程和先裝誰沒有關(guān)系，比如下面先裝C再裝B最后A，按照上面的邏輯一樣的可以得到這個(gè)結(jié)果
?
?
?
1kg
2kg
3kg
4kg
5kg
加入物品C
0
0
0
12
12
加入物品B
0
10
10
12
12
加入物品A
6
10
16
16
18
?
?
上面這個(gè)推導(dǎo)過程總結(jié)起來就是------狀態(tài)轉(zhuǎn)移方程
上面的這個(gè)表的數(shù)據(jù)是不是就是一個(gè)二維數(shù)組，可以得到如下公式
(注意：為了方便代碼實(shí)現(xiàn)，數(shù)組下標(biāo)均從1開始)
Math.max(money[i - 1] + freeMoney , notHaveCurrent)
freeMoney = result[i - 1][currentW - weight[i - 1]];
notHaveCurrent = result[i - 1][currentW];
?
int money[] ={6,10,12}
int weight[] = {1,2,4};
result[][] ????結(jié)果二維數(shù)組
currentW: 當(dāng)前背包容量
freeMoney : 裝完當(dāng)前物品，余下空間的價(jià)值
notHaveCurrent: 不要加入物品的價(jià)值，也就是前面一次的價(jià)值
money[i - 1]：當(dāng)前的物品的價(jià)值
下面就用代碼來實(shí)現(xiàn)這個(gè)邏輯：
public static int dynamicProgramming() { int[] money ={10,6,12}; int[] weight
= {2,1,4}; int w = 5; //包容量 int count = 3; int result[][] = new int
[count+1][w+1];//容量是從1開始，都擴(kuò)大一位防止越界,放置物品也從一開始，因?yàn)榈谝淮我惨∏耙淮蔚臄?shù)據(jù)，保證前一次有默認(rèn)數(shù)據(jù) for (int
i = 1; i <= count; i++) {//依次裝物品 for (int currentW = 1; currentW <= w;
currentW++) {//背包容量依次增加 if (weight[i - 1] <= currentW) { //
當(dāng)前物品的容量小于當(dāng)前背包重量表示可以裝進(jìn)去 int freeMoney = result[i - 1][currentW - weight[i - 1]];
//裝完當(dāng)前物品，余下空間的價(jià)值 int notHaveCurrent = result[i - 1][currentW]; //
不要當(dāng)前物品的價(jià)值，也就是前面一次的價(jià)值 result[i][currentW] = Math.max(money[i - 1] + freeMoney,
notHaveCurrent); }else { //不能裝當(dāng)前 取前一次 result[i][currentW] = result[i - 1
][currentW]; } } }return result[count][w]; }
?
在動態(tài)規(guī)劃中最重要的就是找到狀態(tài)轉(zhuǎn)移方程。可以借助狀態(tài)轉(zhuǎn)移表，來找到狀態(tài)轉(zhuǎn)移方程，比如上面的表格，找到這個(gè)方程之后，基本上就可以用代碼來實(shí)現(xiàn)了。
動態(tài)規(guī)劃是每次都會把當(dāng)前情況下的最優(yōu)解計(jì)算出來，層層遞推，下一層的最優(yōu)解都是基于它上一次結(jié)果存下來的，所以最后一個(gè)結(jié)果就一定是最優(yōu)解。而貪心是指關(guān)心局部，不管后面，上面會議，第一個(gè)會議決定了，后面其實(shí)也就決定了。
熱門工具 換一換