當(dāng)前位置:首頁(yè) > 芯聞號(hào) > 充電吧
[導(dǎo)讀]關(guān)于貪心算法,我聽(tīng)說(shuō)過(guò)好幾次了,但是不知道為什么總是想到貪吃蛇,今天我才知道算法講的什么意思,根據(jù)我們老師的ppt講義,原理很簡(jiǎn)單,大部分都是例子,但是我感覺(jué)掌握還是要下功夫的,重點(diǎn)在于如何針對(duì)特定的

關(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");
???}
}
本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專(zhuān)欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請(qǐng)及時(shí)聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車(chē)的華為或?qū)⒋呱龈蟮莫?dú)角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

倫敦2024年8月29日 /美通社/ -- 英國(guó)汽車(chē)技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車(chē)工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車(chē)。 SODA V工具的開(kāi)發(fā)耗時(shí)1.5...

關(guān)鍵字: 汽車(chē) 人工智能 智能驅(qū)動(dòng) BSP

北京2024年8月28日 /美通社/ -- 越來(lái)越多用戶(hù)希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時(shí)企業(yè)卻面臨越來(lái)越多業(yè)務(wù)中斷的風(fēng)險(xiǎn),如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報(bào)道,騰訊和網(wǎng)易近期正在縮減他們對(duì)日本游戲市場(chǎng)的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國(guó)國(guó)際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)開(kāi)幕式在貴陽(yáng)舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國(guó)國(guó)際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱(chēng),數(shù)字世界的話(huà)語(yǔ)權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn): 有效應(yīng)對(duì)環(huán)境變化,經(jīng)營(yíng)業(yè)績(jī)穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤(rùn)率延續(xù)升勢(shì) 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長(zhǎng) 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競(jìng)爭(zhēng)力 堅(jiān)持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競(jìng)爭(zhēng)優(yōu)勢(shì)...

關(guān)鍵字: 通信 BSP 電信運(yùn)營(yíng)商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺(tái)與中國(guó)電影電視技術(shù)學(xué)會(huì)聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會(huì)上宣布正式成立。 活動(dòng)現(xiàn)場(chǎng) NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長(zhǎng)三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會(huì)上,軟通動(dòng)力信息技術(shù)(集團(tuán))股份有限公司(以下簡(jiǎn)稱(chēng)"軟通動(dòng)力")與長(zhǎng)三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉