0-1背包问题.cpp

前一阵出去玩了

#include <iostream.h>
int min(int a,int b)
{
	if (a<=b)
		return a;
	else
		return b;
}
int max(int a,int b)
{
	if (a>=b)
		return a;
	else
		return b;
}
void Knapsack(int *v,int *w,int c,int n,int **m)
{
	int jMax=min(w[n-1]-1,c);
	for (int j=0;j<=jMax;j++)
		m[n-1][j]=0;
	for (j=w[n-1];j<=c;j++)
		m[n-1][j]=v[n-1];
	for (int i=n-2;i>0;i--)
	{
		jMax=min(w[i]-1,c);
		for (int j=0;j<=jMax;j++)
			m[i][j]=m[i+1][j];
		for (j=w[i];j<=c;j++)
			m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
	}
	if (c>=w[0])
		m[0][c]=max(m[0][c],m[1][c-w[0]]+v[0]);
}
void Traceback (int **m,int *w,int c,int n,int *x)
{
	for (int i=0;i<n-1;i++)
		if(m[i][c]==m[i+1][c])
			x[i]=0;
		else
		{
			x[i]=1;
			c-=w[i];
		}
		x[n-1]=(m[n][c])?1:0;
}
void main()
{
    int c;
	cout<<"请输入背包的重量:"<<endl;
	cin>>c;
	int n;
	cout<<"请输入物品的个数:"<<endl;
	cin>>n;
	int *w=new int[n];
	int *v=new int[n];
	int i;
	cout<<"请输入每个物品的重量:"<<endl;
	for (i=0;i<n;i++)
		cin>>w[i];
	cout<<"请输入每个物品的价值:"<<endl;
	for (i=0;i<n;i++)
		cin>>v[i];
	int *x=new int[n];
    int **m=new int *[n];
	for (i=0;i<=n;i++)
		m[i]=new int[c+1];
	Knapsack(v,w,c,n,m);
	Traceback(m,w,c,n,x);
	cout<<"最优值为:"<<m[0][c]<<endl;
	cout<<"最优解为:";
	for (i=0;i<n-1;i++)
		cout<<x[i]<<",";
	cout<<x[n-1]<<endl;
}