(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	return packet_2;
}



list<Product> SelectFrom(Product product_list[],int pro_num,float allow_weight,float max_weight)
{
	cout<<"pro_num="<<pro_num<<"  allow_weight="<<allow_weight<<"  max_weight="<<max_weight<<endl;////////////////////////
	
	list<Product> packet;
	cout<<"packet has been created!"<<endl;////////////////////////////////


	if(pro_num<=1)
	{
		cout<<"executing condition of pro_num==1!"<<endl;/////////////////////////////
		cout<<"product_list==NULL is"<<(product_list==NULL)<<endl;/////////////////////////
		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 ;
		}
		cout<<"Mybe return:"<<endl;/////////////////
		list<Product>::iterator pos;//////////////
		for(pos=packet.begin ();pos!=packet.end ();pos++)///////////////////////////////
			cout<<pos->product_name <<" ";////////////////////////////////
		cout<<endl;/////////////////////////////

		return packet;
	}
	else
	{
		cout<<"Start to count best selovation!"<<endl;///////////////////////////////
		for(int i=0;i<pro_num;i++)
		{
			cout<<"want to insert weight is:"<<product_list[i].weight <<endl;/////////////////////////////
			cout<<"allow_weight is:"<<allow_weight<<endl;///////////////////////////

			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) 
				{
					int j=0;
					int size=packet.size ();
					cout<<"size="<<size<<endl;////////////////////
					Product *new_product_list=new Product[size];
					list<Product>::iterator pos;
					cout<<"packet.empty() is"<<packet.empty ()<<endl;//////////////
					for(pos=packet.begin ();pos!=packet.end ();pos++)
					{
						cout<<"pos==NULL is"<<(pos==NULL)<<endl;///////////////////
						new_product_list[j++]=*pos;
						cout<<"successfully!"<<endl;/////////////////
					}

					cout<<"j="<<j<<endl;////////////////////////////


					list<Product> new_packet;
					new_packet.push_back (product_list[i]);
//					max_weight-=product_list[i].weight ;
					cout<<"before recall max_weight is:"<<max_weight<<endl;///////////////////////
					list<Product> packet_temp=SelectFrom(new_product_list,j,max_weight-product_list[i].weight  ,max_weight-product_list[i].weight  );
					cout<<"After return,max_weight is:"<<max_weight<<"  allow_weight is:"<<allow_weight<<endl;////////////////////////////
					for(pos=packet_temp.begin ();pos!=packet_temp.end ();pos++)
					{
						new_packet.push_back (*pos);
					}


					cout<<"before select:"<<endl;//////////////////////
					cout<<"allow_weight is:"<<allow_weight<<endl;//////////////////////
					cout<<"max_weight is:"<<max_weight<<endl;///////////////////////////
					for(pos=packet.begin ();pos!=packet.end ();pos++)///////////////////////////////
						cout<<pos->product_name <<" ";////////////////////////////////
					cout<<endl;/////////////////////////////
					

					packet=SelectPriorBetween(packet,new_packet);
					allow_weight=max_weight;
					for(pos=packet.begin();pos!=packet.end();pos++)
					{
						allow_weight-=pos->weight;
					}

					cout<<"after select:"<<endl;//////////////////////
					cout<<"allow_weight is:"<<allow_weight<<endl;////////////////////////
					cout<<"max_weight is:"<<max_weight<<endl;//////////////////
					for(pos=packet.begin ();pos!=packet.end ();pos++)///////////////////////////////
						cout<<pos->product_name <<" ";////////////////////////////////
					cout<<endl;/////////////////////////////
				}
			}
			cout<<"allow_weight is:"<<allow_weight<<endl;/////////////////////
			cout<<"max_weight is:"<<max_weight<<endl;//////////////////////
			cout<<"continue circyling!"<<endl;//////////////////////
			cout<<"Mybe return1:"<<endl;/////////////////
			list<Product>::iterator pos;//////////////
			for(pos=packet.begin ();pos!=packet.end ();pos++)///////////////////////////////
				cout<<pos->product_name <<" ";////////////////////////////////
			cout<<endl;////////////////
		}
		

		cout<<"Now is going to return!"<<endl;///////////////////////////////////
		cout<<"max_weight is:"<<max_weight<<endl;/////////////////////////////
		cout<<"allow_weight is:"<<allow_weight<<endl;/////////////////////////
		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;
	}


	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;
}

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