背包问题.txt

使用C++编写的使用贪心算法来实现的背包问题。

//背包问题
#include<iostream>
using namespace std;
void Sort(int n,float v[],float w[]);
void Knapsack(int n,float M,float v[],float w[],float x[]);

void main()
{
	cout<<"\t\t\t***********************"<<endl;
	cout<<"\t\t\t       背包问题"<<endl;
	cout<<"\t\t\t***********************"<<endl;
	float PackWeight=50;
	float Value[4]={0,360,100,120};//物品依次的价值
	float Weight[4]={0,60,20,30};//物品依次的重量
	float Choose[4];
	Knapsack(3,PackWeight,Value,Weight,Choose);
	for(unsigned short counter=1;counter<=3;counter++)
	{
		cout<<"第"<<counter<<"件物品应该放的百分比是:";
		cout<<Choose[counter];
		cout<<endl;
	}



}
void Knapsack(int OverAll,float  PackWeight,float Value[],float Weight[],float Choose[])
{
	Sort(OverAll,Value,Weight);
	int counter;
	for(counter=1;counter<=OverAll;counter++)
	{
	
		Choose[counter]=0;
		
	}
	for(counter=1;counter<=OverAll;counter++)
	{
		if(Weight[counter]>PackWeight)//如果单位价值最大的物品比背包的重量还要大,则全部放该物品
		{
			break;
		}
		Choose[counter]=1;//如果单位价值最大的物品没有背包能够盛的总量大
		PackWeight=PackWeight-Weight[counter];
	}
	if(counter<=OverAll)
	{
		Choose[counter]=PackWeight/Weight[counter];
	}


}
void Sort(int OverAll,float Value[],float Weight[])
{
/*	float *pWorth=new float[OverAll+1];
	for(unsigned short counter=1;counter<=OverAll;counter++) //float Worth[OverAll];
	{
		pWorth[counter]=Value[counter]/Weight[counter];
	}
	for(counter=1;counter<=OverAll;counter++)
	{
		for(counter1=counter;counter1<=OverAll;counter++)
		{
			if(pWorth)
		
		}
	
	
	}


*/


}