(0-1)背包问题.cpp

计算机算法中著名的0_1背包问题：给定n种物品和一背包。物品i的重量是Wi

// 这是使用应用程序向导生成的 VC++ 
// 应用程序项目的主项目文件。

#include "stdafx.h"

#using <mscorlib.dll>

#include <wjz_execute.h>

using namespace std;


//存储商品的名称、价值和重量
struct Product
{
	string product_name;
	float value;
	float weight;

	Product operator =(const Product &pro)
	{
		product_name=pro.product_name ;
		value=pro.value ;
		weight=pro.weight ;
		return *this;
	}

	bool operator ==(const Product &pro)
	{
		return (product_name==pro.product_name && value==pro.value && weight==pro.weight );
	}
};




//从两个解集中选择一个较优的解集
list<Product> SelectPriorBetween( list<Product> packet_1, list<Product> packet_2 )
{
	float packet_value_1=0.0,packet_value_2=0.0;
	list<Product>::iterator pos;

	for(pos=packet_1.begin ();pos!=packet_1.end ();pos++)
		packet_value_1+=pos->value ;

	for(pos=packet_2.begin ();pos!=packet_2.end ();pos++)
		packet_value_2+=pos->value ;

	if(packet_value_1>packet_value_2)	return packet_1;
	else if(packet_value_2>packet_value_1)	return packet_2;
	else
	{
		if(packet_1.size ()>packet_2.size ())  return packet_1;
		else return packet_2;
	}
}



//函数SelectFrom()用来完成从商品列表product_list中选择商品
list<Product> SelectFrom(Product product_list[],int pro_num,float allow_weight,float max_weight)
{
	
	list<Product> packet;


	if(pro_num<=1)
		//当只能选择的商品不超过一个时，判断是否选择该商品,然后返回
	{
		if(pro_num==0 || product_list[0].weight >max_weight)
			//不能选择该商品或列表中没商品时，插入一个空商品
		{
			Product null_product;
			null_product.product_name ="";
			null_product.value =0.0;
			null_product.weight =0.0;
			packet.push_back (null_product);
		}
		else
			//商品可以被选择则插入该商品
		{
			packet.push_back (product_list[0]);
			allow_weight-=product_list[0].weight ;
		}

		return packet;   //返回
	}
	else
		//商品列表中不只两个商品时，从列表中选择商品
	{
		for(int i=0;i<pro_num;i++)
		{
			if(product_list[i].weight <=allow_weight)
				//背包中剩余的容量允许放入该商品时，放入该商品
			{
				packet.push_back (product_list[i]);
				allow_weight-=product_list[i].weight ;
			}
			else if(product_list[i].weight <=max_weight)
				//背包剩余容量不允许插入该商品，但商品重量未超过最背包的最大允许容量时，才允许求另外一个解集
			{
				if(i>0) 
					//列表中必须至少有一个商品，才求另外一个解集
				{

					//列出可供选择的商品列表new_product_list
					int j=0;
					int size=i ;
					Product *new_product_list=new Product[size];
					for(j=0;j<size;j++)
					{
						new_product_list[j]=product_list[j];
					}


					list<Product> new_packet;       //new_packet用来存放另一个解集
					new_packet.push_back (product_list[i]);

					//将new_product_list传递给函数SelectFrom(),开始求另外一个解集
					list<Product> packet_temp=SelectFrom(new_product_list,j,max_weight-product_list[i].weight  ,max_weight-product_list[i].weight  );
					list<Product>::iterator pos;
					for(pos=packet_temp.begin ();pos!=packet_temp.end ();pos++)
					{
						new_packet.push_back (*pos);
					}


					packet=SelectPriorBetween(packet,new_packet);     //将求出的新解集与原解集比较，从中选择一个最优的

					//重新计算剩余的允许容量
					allow_weight=max_weight;
					for(pos=packet.begin();pos!=packet.end();pos++)
					{
						allow_weight-=pos->weight;
					}
				}
			}
		}	
		return packet;
	}
}



void StartProc(void)
{
	Product *product_list;
	cout<<"请输入商品的数量：";
	int pro_num;
	cin>>pro_num;
	product_list=new Product[pro_num];
	string product_name;
	float value;
	float weight;
	for(int i=0;i<pro_num;i++)
	{
		cout<<"输入商品"<<i+1<<"的名称：";
		cin>>product_name;
		cout<<"输入商品"<<i+1<<"的价值：";
		cin>>value;
		cout<<"输入商品"<<i+1<<"的重量：";
		cin>>weight;
		product_list[i].product_name =product_name;
		product_list[i].value =value;
		product_list[i].weight =weight;
	}


	while(1)
	{
		float allow_weight;
		cout<<"背包的承受值：";
		cin>>allow_weight;

		list<Product> packet;
		packet=SelectFrom(product_list,pro_num,allow_weight,allow_weight);

		cout<<"建议您购买：";
		list<Product>::iterator pos;
		for(pos=packet.begin ();pos!=packet.end ();pos++)
			cout<<pos->product_name <<" ";
		cout<<endl;
		cout<<"\n重新给出商品列表输入1，换背包从原有商品中重选输入2。\n请选择：";
		int selection;
		cin>>selection;
		if(selection==1) break;
	}
}

int _tmain()
{
    // TODO: 请用您自己的代码替换下面的示例代码。
	execute(StartProc);
	return 0;
}