貪心算法在背包中的應(yīng)用
貪心法是一種改進(jìn)了的分級處理方法。用貪心法設(shè)計算法的特點是一步一步地進(jìn)行,根據(jù)某個優(yōu)化測度(可能是目標(biāo)函數(shù),也可能不是目標(biāo)函數(shù)),每一步上都要保證能獲得局部最優(yōu)解。每一步只考慮一個數(shù)據(jù),它的選取應(yīng)滿足局部優(yōu)化條件。若下一個數(shù)據(jù)與部分最優(yōu)解連在一起不再是可行解時,就不把該數(shù)據(jù)添加到部分解中,直到把所有數(shù)據(jù)枚舉完,或者不能再添加為止。這種能夠得到某種度量意義下的最優(yōu)解的分級處理方法稱為貪心法。
選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)度量標(biāo)準(zhǔn)是使用貪心法的核心問題。
假定有n個物體和一個背包,物體i 有質(zhì)量wi,價值為pi,而背包的載荷能力為M。若將物體i的一部分xi(1<=i<=n,0<=xi<=1)裝入背包中,則有價值pi*xi。在約束條件(w1*x1+w2*x2+…………+wn*xn)<=M下使目標(biāo)(p1*x1+p2*x2+……+pn*xn)達(dá)到極大,此處0<=xi<=1,pi>0,1<=i<=n.這個問題稱為背包問題(Knapsack problem)。
要想得到最優(yōu)解,就要在效益增長和背包容量消耗兩者之間尋找平衡。也就是說,總應(yīng)該把那些單位效益最高的物體先放入背包。
在實現(xiàn)算法的程序中,實現(xiàn)算法的核心程序倒沒碰到很大的問題,然而實現(xiàn)尋找最優(yōu)度量標(biāo)準(zhǔn)程序時麻煩不斷!
在尋找最優(yōu)度量標(biāo)準(zhǔn)時,大致方向是用冒泡排序算法。也就是根據(jù)p[i]/w[i]的大小來對w[i]來排序。
在直接用此算法時,可以有如下的一段代碼:
//根據(jù)效益tempArray[i]對重量w[i]排序,為進(jìn)入貪心算法作準(zhǔn)備
1 void sort(float tempArray[], flaot w[], int n)
2 {
3 int i = 0, j = 0;
4 int index = 0;
5
6 //用類似冒泡排序算法,根據(jù)效益p[i]/w[i]對w[i]排序
7 for (i = 0; i < n; i++)
8 {
9 float swapMemory = 0;
10 float temp;
11
12 temp = tempArray[i];
13 index = i;
14
15 for (j = i + 1; j < n; j++)
16 {
17 if (temp < tempArray[j])
相關(guān)推薦:北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |