貪心方法:總是對當前的問題作最好的選擇,也就是局部尋優。最後得到整體最優。
應用:
1:該問題可以通過“局部尋優”逐步過渡到“整體最優”,這是貪心選擇性質與“動態規劃”的主要差別。
2:最優子結構性質:某個問題的整體最優解包含了“子”問題的最優解。
完整的代碼如下:
代碼如下:
#include "iostream"
using namespace std;
struct goodinfo
{
float p; //物品效益
float w; //物品重量
float X; //物品該放的數量
int flag; //物品編號
};//物品信息結構體
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)//當該物品重量大與剩余容量跳出
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++)
{
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<<"最優解為:"<<endl;
for(i=1;i<=n;i++)
{
cout<<"第"<<i<<"件物品要放:";
cout<<goods[i].X<<endl;
}
}
int main(void)
{
cout<<"|--------運用貪心法解背包問題---------|"<<endl;
cout<<"|-------------------------------------|"<<endl;
int i,j,n;
float M;
goodinfo *goods; //定義一個指針
cout<<"press <1> to run the program"<<endl;
cout<<"press <0> to exit"<<endl;
cin>>j;
while(j)
{
cout<<"請輸入物品的總數量:";
cin>>n;
goods=new struct goodinfo [n+1];
cout<<"請輸入背包的最大容量:";
cin>>M;
cout<<endl;
for(i=1;i<=n;i++)
{
goods[i].flag=i;
cout<<"請輸入第"<<i<<"件物品的重量:";
cin>>goods[i].w;
cout<<"請輸入第"<<i<<"件物品的效益:";
cin>>goods[i].p;
goods[i].p=goods[i].p/goods[i].w; //得出物品的效益,重量比
cout<<endl;
}
Insertionsort(goods,n);
bag(goods,M,n);
cout<<"press <1> to run agian"<<endl;
cout<<"press <0> to exit"<<endl;
cin>>j;
}
system("pause");
return 0;
}