1. 貪心算法的基本原理：

貪心算法總是作出在當(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)解。如單源最短路經(jīng)問(wèn)題，最小生成樹(shù)問(wèn)題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。?

貪心算法求解的問(wèn)題一般具有兩個(gè)重要性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

（1）所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)解的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。

（2）當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。

（2）背包問(wèn)題的貪心算法實(shí)現(xiàn)

算法實(shí)現(xiàn)主要代碼如下：

#include <iostream.h>

#include <string>

#include <conio.h>

using namespace std;

?

//物品信息結(jié)構(gòu)體

struct goodinfo

{

????float p; //物品效益

????float w; //物品重量

????float X; //物品該放的數(shù)量

????int flag; //物品編號(hào)

};

?

//*********按物品效益，重量比值做升序排列***************//

void Insertionsort(goodinfo goods[],int n)

{

????int j,i;

????for(j=2;j<=n;j++)

????{

????????goods[0]=goods[j];

????????i=j-1;

????????while (goods[0].p>goods[i].p)

????????{

????????????goods[i+1]=goods[i];

????????????i--;

????????}

????????goods[i+1]=goods[0];

????}

}

?

//*********將物品放入背包**************//

void bag(goodinfo goods[],float M,int n)

{

????float cu;

????int i,j;

????for(i=1;i<=n;i++)

????????goods[i].X=0;

????cu=M; //背包剩余容量

????for(i=1;i<n;i++)

????{

????????if(goods[i].w>cu)//當(dāng)該物品重量大與剩余容量跳出

????????????break;

????????goods[i].X=1;

????????cu=cu-goods[i].w;//確定背包新的剩余容量

????}

????if(i<=n) goods[i].X=cu/goods[i].w;//該物品所要放的量

????for(j=2;j<=n;j++) /*按物品編號(hào)做降序排列*/

????{

????????goods[0]=goods[j];

????????i=j-1;

????????while (goods[0].flag<goods[i].flag)

????????{

????????????goods[i+1]=goods[i];

????????????i--;

????????}

????????goods[i+1]=goods[0];

????}

????cout<<"最優(yōu)解為:"<<endl;

????for(i=1;i<=n;i++)

????{

????????cout<<"第"<<i<<"件物品要放:";

????????cout<<goods[i].X<<endl;

????}

}

?

//*************主函數(shù)***************//

void main()

{

????int n;

char j;

????float M;

????goodinfo *goods;//定義一個(gè)指針

????cout<<"#####背包問(wèn)題的貪心算法#####\n"<<endl;

?

????while(!(j=='n'||j=='N'))

????{

????????cout<<"物品的種類(lèi)數(shù)量：";

????????cin>>n;

????????goods=new struct goodinfo [n+1];//

????????cout<<"背包的最大容量：";

????????cin>>M;

????????cout<<endl;

????????int i;

????????for(i=1;i<=n;i++)

????????{

????????????goods[i].flag=i;

????????????cout<<"第"<<i<<"件物品:"<<endl;

????????????cout<<"重量:";

????????????cin>>goods[i].w;

????????????cout<<"價(jià)值:";

????????????cin>>goods[i].p;

????????????goods[i].p=goods[i].p/goods[i].w;//得出物品的重量比

????????????cout<<endl;

????????}

????????Insertionsort(goods,n);

????????bag(goods,M,n);

????????

????????cout<<endl<<"是否繼續(xù)（y/n）？"<<endl;

????????j= getch();

????????cout<<"---------------------"<<endl;

????}

}

編譯并運(yùn)行程序。

（3）算法的時(shí)間復(fù)雜性和空間復(fù)雜性

以上算法的時(shí)間復(fù)雜度和空間復(fù)雜度為O(n²)，其中時(shí)間復(fù)雜度基本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度可以優(yōu)化到O(n)。

程序運(yùn)行結(jié)果如下：

注意背包問(wèn)題與0-1背包問(wèn)題的不同，雖然這兩個(gè)問(wèn)題極為相似，但背包問(wèn)題可以用貪心算法求解，而對(duì)于0-1背包問(wèn)題，貪心選擇算法不能得到最優(yōu)解。因?yàn)樵?-1背包問(wèn)題的這種情況下，它無(wú)法保證最后能將背包裝滿，部分閑置的背包空間，使每公斤背包的價(jià)值降低了。動(dòng)態(tài)規(guī)劃算法可以有效的解0-1背包問(wèn)題。