bag.cpp

常用算法与数据结构原代码

#include <iostream.h>
#define N 100

double limitW,totV,maxv;
int option[N],cop[N];
struct {
	double weight;
	double value;
} a[N];
int n;

void Try(int i,double tw,double tv)
{
	int k;
	if (tw+a[i].weight<=limitW)
	{
		cop[i]=1;
		if (i<n-1)
			Try(i+1,tw+a[i].weight,tv);
		else
		{
			for (k=0;k<n;k++)
				option[k]=cop[k];
			maxv=tv;
		}
		cop[i]=0;
	}
	if (tv-a[i].value>maxv)
		if (i<n-1)
			Try(i+1,tw,tv-a[i].value);
		else
		{
			for (k=0;k<n;k++)
				option[k]=cop[k];
			maxv=tv-a[i].value;
		}
}

void main()
{
	int k;
	double w,v;
	cout<<"输入物品种数"<<endl;
	cin>>n;
	cout<<"输入各物品的重量和价值"<<endl;
	for (totV=0,k=0;k<n;k++)
	{
		cin>>w >>v;
		a[k].weight=w;
		a[k].value=v;
		totV+=v;
	}
	cout<<"输入限制重量"<<endl;
	cin>>limitW;
	maxv=0;
	for (k=0;k<n;k++)
		cop[k]=0;
	Try(0,0,totV);
	for (k=0;k<n;k++)
		if (option[k])
			cout<<k+1<<endl;
	cout<<"总价值为 "<<maxv<<endl;
}