knapsack.cpp

谈心算法实现0/1背包问题的解决

// Knapsack.cpp: implementation of the Knapsack class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Knapsack.h"
#include "iostream.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

//##ModelId=46189AD600DB
Knapsack::Knapsack()
{
	contain=0;
	num=0;
//	a=NULL;
}

//##ModelId=46189AD600DF
Knapsack::~Knapsack()
{
	delete a;
	delete sorted;
}

//##ModelId=46189AD600DC
void Knapsack::Init_Knapsacl()
{
	cout<<"请输入背包容量:";
	cin>>contain;
	cout<<"请输入物品数量:";
	cin>>num;
	a=new item[num];
	sorted=new int[num];
	int i;
	for(i=0;i<num;i++)
	{
		cout<<"请输入物品"<<i+1<<"的重量:";
		cin>>a[i].weight;
		cout<<"请输入物品"<<i+1<<"的价值:";
		cin>>a[i].value;
		a[i].p=a[i].value/a[i].weight;
		sorted[i]=i;
	}
	Sort_Knapsacl();
}

//##ModelId=46189AD600DE
void Knapsack::Sort_Knapsacl()
{
	int i,j;
	for(i=0;i<num;i++)
		for(j=0;j<num-i-1;j++)
		{
			if(a[j].p<a[j+1].p)
			{
				item b;
				int  c;
				c=sorted[j];
				sorted[j]=sorted[j+1];
				sorted[j+1]=c;
				b.p=a[j].p;
				b.value=a[j].value;
				b.weight=a[j].weight;
				a[j].p=a[j+1].p;
				a[j].value=a[j+1].value;
				a[j].weight=a[j+1].weight;
				a[j+1].p=b.p;
				a[j+1].value=b.value;
				a[j+1].weight=b.weight;
			}
		}

}

//##ModelId=46189AD600DD
void Knapsack::Most_Valuable()
{
	int i,c;
	c=contain;
	for(i=0;i<num;i++)
	{
		if(c-a[i].weight<0)
		{
			cout<<"物品"<<sorted[i]+1<<"\t"<<c<<endl;
			c=0;
			break;
		}
		else
		{
			c=c-a[i].weight;
			cout<<"物品"<<sorted[i]+1<<"\t"<<a[i].weight<<endl;
		}
	}
}