0-1背包.cpp

解决背包的取舍问题

#include "iostream.h"

int min(int a,int b)
{
 if(a>=b)  return b;
 else  return a;
}

int max(int a,int b)
{
 if(a>=b)   return a;
 else return b;
}

void Knapsack(int v[6],int w[6],int c,int n,int m[6][6])
{
 int jmax=min(w[n]-1,c);

 for(int j=0;j<jmax;j++)
	 m[n][j]=0;
 for(int p=w[n];p<=c;p++)
	 m[n][p]=v[n];

 for(int i=n-1;i>1;i--)
 {
	jmax=min(w[i]-1,c);
   for(int j=0;j<=jmax;j++)
	 m[i][j]=m[i+1][j];

   for(int t=w[i];t<=c;t++)
	   m[i][t]=max(m[i+1][t],m[i+1][t-w[i]]+v[i]);
 }
   m[1][c]=m[2][c];
   if(c>=w[1])
	   m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);

}

void Traceback(int m[6][6],int w[6],int c,int n,int x[6])
{
  for(int i=1;i<n;i++)
	  if(m[i][c]==m[i+1][c]) x[i]=0;

	else 
	{
	  x[i]=1;
	  c-=w[i];
	}
	x[n]=(m[n][c]!=0)?1:0;
}

void main()
{
  int n1=5;
  int c1;
  int w1[6]={0,2,2,6,5,4};
  int v1[6]={0,6,3,5,4,6};
  int t[6][6];
  int x1[6];

  cout<<"请输入背包的容量："<<endl;
  cin>>c1;

  cout<<"0-1背包问题是："<<endl;
  cout<<"物品的重量分别为："<<endl;
  for(int p=1;p<6;p++)
	  cout<<w1[p]<<" ";

  cout<<endl;

  cout<<"物品的价值分别为："<<endl;
  for(int q=1;q<6;q++)
	  cout<<v1[q]<<" ";

   cout<<endl;

  cout<<"背包的容量为："<<c1<<endl;
  cout<<"要选择的物品是:"<<endl;

  Knapsack(v1,w1,c1,n1,t);
  Traceback(t,w1,c1,n1,x1);

 for(int i=1;i<=n1;i++)
	 if(x1[i]==1)
	 cout<<"第"<<i<<"件物品"<<"\t";
}