现在的位置: 首页 > 综合 > 正文

0-1背包问题、背包问题(贪心算法)

2013年06月01日 ⁄ 综合 ⁄ 共 3291字 ⁄ 字号 评论关闭

#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();
}

抱歉!评论已关闭.