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