beibao.cpp

一个实现背包的简单源程序.自己编的,有点简单,提供给初学者参考.

#include <iostream.h>
int w[6]={0,1,2,3,4,5};
int v[6]={0,1,2,3,4,5};
int c[6][11]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};


void main ()
{
	int i,j,aw(10);
	cout<<"各个物品的重量为：";
	for(i=1;i<6;i++)
		cout<<w[i]<<',';
	cout<<endl;
	cout<<"各个物品的价值为：";
	for(i=1;i<6;i++)
		cout<<v[i]<<',';
	cout<<endl<<endl;
	void knapsack(int n,int aw);
	knapsack(5,aw);
	cout<<"二维表的内容为："<<endl;
	for(i=1;i<6;i++)
	{
		for(j=0;j<=aw;j++)
			cout<<c[i][j]<<',';
		cout<<endl;
	}
	cout<<endl;
	void output(int aw);
	output(aw);
}


void knapsack(int n,int aw)
{
	int i,j,m;
	for(i=1;i<=n;i++)
	{
		c[i][0]=0;
		for(m=1;m<=10;m++)
		{
			if(w[i]<=m)
			{
				j=c[i-1][m-w[i]]+v[i];
				if(j>c[i-1][m])
					c[i][m]=j;
				else 
					c[i][m]=c[i-1][m];
			}
			else
				c[i][m]=c[i-1][m];
		}
	}
}




void output(int aw)
{
	int i,x[6];
	for (i=5;i>1;i--)
	{
		if(c[i][aw]==c[i-1][aw])
			x[i]=0;
		else 
		{
			x[i]=1;
			aw=aw-w[i];
		}
	}
	x[1]=c[1][aw]?1:0;
	cout<<"物品的选择情况为："<<endl;
	for(i=1;i<6;i++)
		cout<<x[i];
	cout<<endl;
}