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



void PutInTo(list<Product>*,Product,float&,float,Product*);



void SelectFrom(Product product_list[],int pro_num,list<Product> *to_packet,float rest_allow_weight,const float allow_weight,Product *pro_must_put_in)
{
	cout<<"SelectFrom->rest_allow_weight="<<rest_allow_weight<<endl;///////////////////
	for(int i=0;i<pro_num;i++)
	{
		PutInTo(to_packet,product_list[i],rest_allow_weight,allow_weight,pro_must_put_in);
	}
}




void PutInTo(list<Product> *packet,Product pro,float &rest_allow_weight,const float allow_weight,Product *pro_must_put_in)
{
	if(pro.weight <=rest_allow_weight)
	{
		packet->push_back (pro);
		rest_allow_weight-=pro.weight ;

		cout<<"rest_allow_weight="<<rest_allow_weight<<endl;

		return;
	}
	else if(pro.weight >allow_weight)
	{
		cout<<"retrun"<<endl;/////////////////
		return;
	}
	else
	{
		cout<<"??"<<endl;////////////////////////////
		rest_allow_weight=allow_weight;

		int pro_num=packet->size ();
		cout<<"pro_num="<<pro_num<<endl;///////////////////

		Product *product_list=new Product[pro_num];
		list<Product>::iterator pos;
		int i=0;
		for(pos=packet->begin ();!packet->empty () && pos!=packet->end ()  ;pos++)
		{
			if(pro_must_put_in!=NULL && *pos==*pro_must_put_in)  pos++;
			if(pos!=packet->end ()) product_list[i++]=*pos;
			else break;
			cout<<"for->?"<<endl;///////////////////////////
		}

		list<Product> *standby_packet=new list<Product>;

		if(pro_must_put_in!=NULL)
		{
			standby_packet->push_back (*pro_must_put_in);
			rest_allow_weight-=pro_must_put_in->weight ;
		}

		if(product_list==NULL) return;

		for(pos=standby_packet->begin ();pos!=standby_packet->end ();pos++) ////////////////////////////////
			cout<<pos->product_name <<" ";  //////////////////////////////
		cout<<endl; ///////////////////////////////

		if(pro.weight <=rest_allow_weight)
		{
			standby_packet->push_back (pro);
			rest_allow_weight-=pro.weight ;
			SelectFrom(product_list,pro_num,standby_packet,rest_allow_weight ,allow_weight,&pro);
		}

		packet=SelectPriorBetween(standby_packet,packet);
		return;
	}
}


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=new list<Product>;
	SelectFrom(product_list,pro_num,packet,allow_weight,allow_weight,NULL);

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