關(guān)于貪心算法，我聽(tīng)說(shuō)過(guò)好幾次了，但是不知道為什么總是想到貪吃蛇，今天我才知道算法講的什么意思，根據(jù)我們老師的ppt講義，原理很簡(jiǎn)單，大部分都是例子，但是我感覺(jué)掌握還是要下功夫的，重點(diǎn)在于如何針對(duì)特定的問(wèn)題進(jìn)行貪心，某類(lèi)問(wèn)題是否適合用貪心算法計(jì)算，這兩點(diǎn)感覺(jué)是難點(diǎn)。
算法思想
顧名思義，貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路徑問(wèn)題，最小生成樹(shù)問(wèn)題等。
在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。
話(huà)雖這樣說(shuō)，但是我感覺(jué)還是存在很多疑惑，因?yàn)槎际菍?duì)特定的問(wèn)題求解，我自然聯(lián)想到了前面學(xué)習(xí)的枚舉類(lèi)型的使用，看了幾個(gè)ppt的例子，無(wú)意間想到了前面枚舉應(yīng)用的時(shí)候那
個(gè)“01背包問(wèn)題”，是否可以用貪心算法來(lái)解決？我的思考是不行，因?yàn)槲易约耗軌蛘业饺绻秘澬乃愠鲥e(cuò)誤結(jié)果的情況，而且是很好列舉的。貪心算法解決的問(wèn)題是否可以用枚
舉的方式來(lái)解決，枚舉算法解決的問(wèn)題是否又可以用貪心算法來(lái)解決，如果兩者都可以的話(huà)，那個(gè)效率會(huì)更高？如果對(duì)于一類(lèi)問(wèn)題只能用這兩種辦法其中的一個(gè)進(jìn)行處理，原因是
什么？這些都是我不知的，也是要學(xué)習(xí)的。
下面是里面的一些案例
1.最優(yōu)裝載問(wèn)題
有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問(wèn)題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。
思路：根據(jù)貪心算法的思想，這里應(yīng)該是每次先選擇小的先裝上，一直到超過(guò)限制就停止，最后輸出編號(hào)就行了。代碼不難，如下：
#include#includetypedef?struct//定義集裝箱結(jié)構(gòu)體
{
????int?weight;
????int?num;
}W;
int?comp(const?void*a,const?void?*b)
{
????return?((W*)a)->weight-((W*)b)->weight;
}
int?main()
{
????W?a[10];
????int?i,j=0;
????int?n=0;
????int?m;
????int?sum=0;
????printf("請(qǐng)輸入集裝箱的個(gè)數(shù):n");//方便測(cè)試不超過(guò)10
????scanf("%d",&m);
????printf("輸入重量的最大限制:n");
????scanf("%d",&n);
????printf("請(qǐng)輸入每個(gè)集裝箱的重量");
????for(i=0;i<m;i++)
????{
????????scanf("%d",&a[i].weight);
????????a[i].num=i+1;
????}
????qsort(a,m,sizeof(W),comp);//先排序
????for(i=0;i<m;i++)//然后從小到大加起來(lái)
????{
????????if(sum<=n)
????????sum+=a[i].weight;
????????else
????????{
????????????j=i;
????????????break;//記錄最后的值
????????}
????}
????for(i=0;i<j;i++)
????{
????????printf("第%d號(hào):?%dn",a[i].num,a[i].weight);
????}
????return?0;
}
2背包問(wèn)題
這個(gè)問(wèn)題和前面枚舉里面提到的背包問(wèn)題很類(lèi)似，但是不是一個(gè)問(wèn)題。
現(xiàn)在有很多物品（它們是可以分割的），我們知道它們每個(gè)物品的單位重量的價(jià)值v和重w（1<=v,w<=10）；如果給你一個(gè)背包它能容納的重量為m（10<=m<=20）,你所要做的就是把物品裝到背包里，使背包里的物品的價(jià)值總和最大。
最大的區(qū)別就是背包問(wèn)題里面提到的物品是可以分割的，物品的價(jià)值是單位重量的價(jià)值，枚舉類(lèi)型的01背包問(wèn)題，01背包問(wèn)題的價(jià)值是物品的價(jià)值，物品是不可以分割的。
因?yàn)椴豢煞指?，所以所以產(chǎn)生的解應(yīng)該是分立的，不是連續(xù)的，有窮個(gè)，但是如果是可以分割，可能情況為無(wú)窮多種，所以這里不適合枚舉。這樣情況下用貪心算法好。在既可
以用枚舉的情況下，用可以用貪心的情況下，枚舉無(wú)疑是最精確的，貪心算法只能求最優(yōu)解的近似解，自己目前還不能針對(duì)具體情況分的非常清楚，只能根據(jù)ppt里提到的及幾
種貪心算法的幾個(gè)實(shí)例。以后繼續(xù)學(xué)習(xí)。
#include#includetypedef?struct
{
????int?val;//單位價(jià)值
????int?weight;
}PRO;
int?comp(const?void?*a,const?void?*b)
{
????return?((PRO*)b)->val-((PRO*)a)->val;
}
int?main()
{
????PRO?a[10];
????int?i=0;
????int?m,n;
????int?val_sum=0;
????int?weight_sum=0;
????printf("輸入物品種類(lèi)數(shù)目:n");
????scanf("%d",&n);
????printf("依次輸入重量和價(jià)值:n");
????for(i=0;i<n;i++)
????{
????????scanf("%d?%d",&a[i].weight,&a[i].val);
????}
????printf("輸入重量的限制:n");
????scanf("%d",&m);
????qsort(a,n,sizeof(PRO),comp);
????for(i=0;i<n&&(weight_summ)
????{
????????val_sum-=(weight_sum-m)*a[i-1].val;
????}
????printf("%d",val_sum);
}虧損問(wèn)題 題目的意思就是如果公司盈利，那么就盈利s，如果虧損，那么就虧損d。但是公司只是5個(gè)月結(jié)算一次，也就是說(shuō)是1——5月，2——6 月……，只結(jié)算這8次。但是公司的這一年的8次結(jié)算下來(lái)，公司都是虧損了，問(wèn)，公司這一年是否能夠盈利，如果能，求出最大的盈利利潤(rùn)，如果不能，則輸出Deficit。
第一眼一看，實(shí)在是看不出和前面的貪心算法有什么聯(lián)系，而且感覺(jué)肯定是賠定了。但是不是。
分析思路
取每次總結(jié)的5個(gè)月份，進(jìn)行排列組合應(yīng)該沒(méi)有先后順序，因?yàn)榫褪沁M(jìn)行加法計(jì)算，減法計(jì)算，賺和賠的順序無(wú)關(guān)緊要（對(duì)于一次調(diào)查來(lái)說(shuō)）
只可能是下列結(jié)果,沒(méi)有其他的了
s s s s d ? ?4*s-d<0
s s s d d ? ? 3*s-2*d<0
s s d d d ? ? 2*s-3*d<0
s d d d d ? ?s-4*d<0
如果這些里面沒(méi)有賺錢(qián)的，這個(gè)公司不可能賺錢(qián)了
如果賺錢(qián)的或者最賺錢(qián)的存在肯定是上面情況的一種，一年內(nèi)賺錢(qián)最多的是上面某一種，那么按照保證每次調(diào)查都是上面的形式就可以保證賺錢(qián)最大了。
s s s s d?s s s s d s s
s s s d d ?s s s d d s s
s s d d d?s s d d d s s
s d d d d?s d d d d ?s d?
可見(jiàn)只要計(jì)算根據(jù)上面情況下s和d是不是也滿(mǎn)足相應(yīng)的條件就行，如果滿(mǎn)足就把12個(gè)月的加起來(lái)，看看是不是賺，然后找出賺的最大值就行了。
#include#includeint?main()
{
???int?s,d,i,j,tem=0;
???int?max_val=0;
???printf("輸入賺錢(qián)和賠錢(qián)的數(shù)目n");
???scanf("%d?%d",&s,&d);
???for(i=1;i<5;i++)
???{
???????tem=(5-i)*s-i*d;
???????if(tem=2)
???????????{
???????????????tem=tem*2+2*s;
???????????}
???????????else
???????????{
???????????????tem=tem*2+s-d;
???????????}
???????????if(max_val0)
???{
???????printf("賺錢(qián)n");
???????printf("%d*s-%d*dn",j,5-j);
???????printf("%d",max_val);
???}
???else
???{
???????printf("賠錢(qián)n");
???}
} 
下載文檔
