#include "iostream.h"
#include "iomanip.h"
typedef float Status;
typedef float Element;
int num;//物品个数
float c;//背包容量(即背包所能容纳的物品总重量)
static float value(0);//当前背包中所有货品的总价值
class Object
{
public :
int id;
Element weight;
Element price;
Element avg_p;
Element in_knapsack_Weight;//该物品已经放入背包中的重量
void avg_price()
{
avg_p=price/weight;
}
};
Object obj[6];//对象数组 ???如何动态的为对象数组分配内存空间???
//目前可用物体数目为 5*******************
void input(int n)
{
for(int i=1;i<=n;i++)
{
cout<<"\n请依次输入第"<<i<<"个物体的重量和价格"<<endl;
cin>>obj[i].weight>>obj[i].price;
obj[i].id=i;
obj[i].avg_price();
}
cout<<endl;
}
void output(int n)
{
for(int i=1;i<=n;i++)
{
cout<<"你所输入的第"<<obj[i].id<<"个物体的"<<endl;
cout<<"重量\t价格\t单价"<<endl;
cout<<obj[i].weight<<"\t"<<obj[i].price<<"\t"<<setprecision(4)<<obj[i].avg_p;
//setprecision(n)用于显示n位有效位数,使用时必须引用头文件 iomanip.h
cout<<endl;
}
}
//将单价由高到低进行排序
void compositor(int num)
{
Object tem;
for(int j=1;j<num;j++)
for(int i=1;i<=num-j;i++)
{
if(obj[i].avg_p<obj[i+1].avg_p)
{
tem=obj[i+1];
obj[i+1]=obj[i];
obj[i]=tem;
}
}
}
//往背包中放入物品,分为两种情况:
//情况1 :(0-1背包算法)所指定种类的物品要么全放进去要么一点儿都不放进去;
//情况2 :(背包算法)要么都可以放进去一部分或者全部.
//情况1执行代码:
void beibao_0_1(Status c,Status &value)
{
value=0;
for(int i=1;i<=num;i++)
{
if( obj[i].weight>c)
continue;
else
{
obj[i].in_knapsack_Weight=obj[i].weight;
value+=obj[i].weight*obj[i].avg_p;
c-=obj[i].weight;
}
}
cout<<"\n放入了背包中的物品情况如下\n";
for( i=1;i<=num;i++)
{
if(obj[i].in_knapsack_Weight>0)
{
cout<<"\t物品" << obj[i].id<<"放入的重量为 "<<obj[i].in_knapsack_Weight<<" ,其价值为 "<<obj[i].price<<endl;
}
}
}
//情况2执行代码:
void beibao(Status c,Status &value)
{
value=0;
for(int i=1;i<=num;i++)
{
if( obj[i].weight>=c)
{
obj[i].in_knapsack_Weight=c;
value+=c*obj[i].avg_p;
break;
}
else
{
obj[i].in_knapsack_Weight=obj[i].weight;
value+=obj[i].weight*obj[i].avg_p;
c-=obj[i].weight;
}
}
cout<<"\n放入了背包中的物品情况如下\n";
for( i=1;i<=num;i++)
{
if(obj[i].in_knapsack_Weight>0)
{ Status z;
z=obj[i].in_knapsack_Weight*obj[i].avg_p ;
cout<<"\t物品" << obj[i].id<<"放入的重量为 "<<obj[i].in_knapsack_Weight<<" ,其价值为 "<<z<<endl;
}
}
}
void chose_operator()
{
loop:
cout<<"\n\t=========请选择一种算法============"<<endl;
cout<<" 1----- 0-1 背包算法 2-----背包算法 3(或者其他键)------Exit "<<endl;
int n;
cin>>n;
switch(n)
{
case 1: {//0-1背包算法
loop2: cout<<"\n=====0-1背包算法===== ";
beibao_0_1(c,value);
cout<<"背包容量为 "<<c<<" ,背包内的物品总价值为 "<<value<<" 元\n\n";
cout<<"想看一下另一种算法吗?(Y/N)\n";
char z;
cin>>z;
if( z-'Y'==0 || z-'Y'==32)
{
goto loop1;
}
else
if( z-'N'!=0 || z-'n'!=32 )
{
cout<<"您的输入有误!"<<endl;
}
};break;
case 2: {//背包算法
loop1: cout<<"\n=====背包算法===== ";
beibao(c,value);
cout<<"背包容量为 "<<c<<" ,背包内的物品总价值为 "<<value<<" 元\n";
cout<<"想看一下另一种算法吗?(Y/N)\n";
char z;
cin>>z;
if( z-'Y'==0 )
{
goto loop2;
}
else
if( z-'N'!=0 )
{
cout<<"您的输入有误!,程序退出!"<<endl;
}
};break;
case 3: break;
default:
{
cout<<"输入有误,请重试!\n";
goto loop;
}
}
}
void main()
{
cout<< "\n\t============贪心算法-背包问题============"<<endl;
cout<<" 请输入物品个数"<<endl;
cin>>num;
input(num);
output(num);
compositor(num);
cout<<"\n----------排序后:"<<endl;
output(num);
cout<<"\n 请输入背包的容量(kg)\n";
cin>>c;
chose_operator();
}