////0-1背包问题
//#include<iostream>
//using namespace std;
//int w[1000],v[1000];
//int f[1000];
//int main()
//{
// int n;//物品数量
// int c;//背包容量
// while(cin>>n)
// {
// for(int i=0;i<n;i++)
// {
// cin>>w[i];//重量
// cin>>v[i];//价值
// }
// memset(f,0,sizeof(f));
// for(int i=0;i<n;i++)
// {
// for(int j=c;j>=v[i];j--)
// {
// f[j]=max(f[j],f[j-w[i]+v[i]);
// }
// }
// cout<<f[c]<<endl;
// }
//}
////背包问题
#include<iostream>
using namespace std;
struct goodinfo
{
float p;//物品价值
float w;//物品重量
float x;//物品该放的数量
int flag;//物品编号
};//物品信息结构体
void insertionsort(goodinfo goods[],int n)//插入排序，按pi/wi价值进行排序
{
int i,j;
for(j=2;j<=n;j++)
{
goods[0]=goods[j];
i=j-1;
while(goods[0].p>goods[i].p)
{
goods[i+1]=goods[0];
}
goods[i+1]=goods[i];i--;
}
}
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)//若不超过容量，增加物品
{
goods[i].x=1;
cu-=goods[i].w;//确定背包新的剩余容量
}
else
{
goods[i].x=0;
}
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()
{
cout<<"贪心算法背包问题"<<endl;
int j,n;
float M;
goodinfo*goods;//定义指针
while(j)
{
cout<<"请输入物品总重量";
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件物品重量";
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 again"<<endl;
cout<<"press 0 to exit"<<endl;
cin>>j;
}
}
贪心背包和0-1背包问题,布布扣,bubuko.com
贪心背包和0-1背包问题
原文：http://blog.csdn.net/u013240812/article/details/23780573
