01背包.cpp

这是学习动态规划时用动态规划设计分析实际问题

#include"iostream"
using namespace std;
#define C 22
#define N 5
//int s[N]={2,3,4,5};//存放物品的体积
//int v[N]={3,4,5,7};//存放物品的价值
int s[N+1];
int v[N+1];
int m[N+1][C+1];
int H[N+1][C+1];
int  max(int a,int b)
{
	int z=a>b?a:b;
	return z;
}
void Knapsack(int c,int n)
{
	int i;
	for( i=1;i<=n;i++)
		for(int j=1;j<=c;j++)
		{
			m[i][j]=m[i-1][j];
		if(s[i]<=j)
		{	
			m[i][j]=max(m[i][j],m[i-1][j-s[i]]+v[i]);
			H[i][j]=1;
		}
		else 
			H[i][j]=0;

		}
}
void Traceback(int n,int c,int x[])
{
	for(int i=n;i>0;i--)
	{
		if(m[i][c]>m[i-1][c]){x[i]=1;c=c-s[i];}
		else x[i]=0;
	}
}
int main()
{
	int i;
	cout<<"输入物品的体积:";
	for( i=1;i<=N;i++)
	cin>>s[i];
	cout<<"输入物品的价值:";
	for(i=1;i<=N;i++)
	cin>>v[i];

	
//	v[N]={3,4,5,7};
	int x[N+1]={0};
	Knapsack(C, N);

	cout<<endl<<"m:"<<endl;
	for( i=1; i<=N; i++)
	{
		for(int j=1;j<=C;j++) 
			printf("%3d",m[i][j]);
		cout<<endl;
	}


	cout<<endl<<endl<<"H:"<<endl;
	for( i=1; i<=N; i++)
	{
		for(int j=1;j<=C;j++) cout<<H[i][j]<<"  ";
		cout<<endl;
	}
	Traceback(N,C,x);
//	int s1=0, v1=0;
//	cout<<"C = "<<C<<endl;
	cout<<"存放的物品最优x:"<<endl;
	for(i=1; i<=N; i++)
	{
		if(x[i]==1)
		cout<<"第"<<i<<"个"<<":体积 "<<s[i]<<"  价值"<<v[i]<<endl;
	//	cout<<s[i]<<" "<<v[i]; 
	//	s1+=x[i]*s[i];
	//	v1+=x[i]*v[i];
	}
	cout<<endl;


	return 0;
}