经典算法问题

#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 *x)
{	
	int max,**m;

	m=new int*[n+1];
	for(int j=0;j<n+1;j++)
		m[j]=new int[c+1];


	for (int i=0;i<=n;i++)
	{
		m[i][0] = 0;
		x[i]=0;
	}
	for (i=0;i<=c;i++)
		m[0][i]=0;
	for (i=1;i<=n;i++)
	{
		for(j=1;j<=c;j++)
		{
			m[i][j] = m[i-1][j];
			if((j>=w[i])&&( m[i-1][j-w[i]]+v[i] )> m[i-1][j])
				m[i][j] = m[i-1][j-w[i]]+v[i];
		}
	}

	j = c;
	for (i=n;i>0;i--)
	{
		if(m[i][j]>m[i-1][j])
		{
			x[i]=1;
			j=j-w[i];
		}
	}

	max=m[n][c];

	cout<<"背包能装载的最大价值是:"<<max<<endl;

	cout<<"背包中应放入的物品为:";

	for (j=0; j<n+1; j++)
		if(x[j] ==1)
			cout<<j<<" ";

	cout<<endl;

}


int main()
{

	int *x;
	int n,c,*w,*v;

	cout<<"      -------------------------背包问题---------------------"<<endl;
	cout<<endl;
	cout<<"      程序功能：运用动态规划算法求解背包问题。"<<endl;
	cout<<"      输入:包的最大承受重量和物品个数以及各个物品的重量和价值。"<<endl;
	cout<<"      输出:背包能装载的最大价值和应该放进去的物品。"<<endl;
	cout<<endl;


	cout<<"请输入物品个数:";
	cin>>n;
	cout<<"请输入背包容量:";
	cin>>c;

	w=new int[n+1];
	v=new int[n+1];
	x=new int[n+1];
	
	for(int k=0;k<n;k++)
	{
		x[k]=0;
	}


	for (int i=1; i<n+1; i++)
	{
		cout<<"请输入第"<<i<<"个物品的重量和价值：";
		cin>>w[i]>>v[i];
	}
	Knapsack(v,w,c,n,x);
	
	return 0;
}