zero_one_question.cpp

来自「算法中的经典问题：0——1 背包问题 在该程序中运用了动态规划算法成功解决了0」· C++ 代码 · 共 73 行

#include<iostream.h>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)

void Knapsack(int *v,int *w,int c,int m[101][101],int vlen,int wlen);
void Traceback(int m[101][101],int *w,int c,int *x,int wlen);

void main()
{
	int n,c,w[100],v[100],x[100];
	int wlen;
	int m[101][101];
	  cout<<"Please input the object number:";
	  cin>>n;
	  cout<<"Please input the c:";
	  cin>>c;
	  cout<<"\nAnd the weight:";
	  wlen = n;
	  for(int i=0;i<n;i++)
		  cin>>w[i];
	  cout<<"\nAnd the value:";
	  for(int j=0;j<n;j++)
		  cin>>v[j];
	  Knapsack(v,w,c,m,wlen,wlen);
	  Traceback(m,w,c,x,wlen);
	  cout<<"Information about object:\n";
	  cout<<"Object weight:";
	  for(int r=0;r<wlen;r++)
		  cout<<w[r]<<"  ";
      cout<<"\nObject value:";
	  for(int t=0;t<wlen;t++)
		  cout<<v[t]<<"  ";
	  cout<<"\nand the content is "<<c<<endl;
	  cout<<"The key is:\n";
	  for(int k=1;k<n;k++)
	  {
		  if (x[k])
		     cout<<"take in the object No."<<k+1<<endl;
	  }
}

void Knapsack(int *v,int *w,int c,int m[101][101],int vlen,int wlen)
{
    int n = vlen-1;
	int jMax = min(w[n]-1,c);

	  for(int j = 0;j<jMax+1;j++) 
		  m[n][j]=0;
	  for(int j1=w[n];j1<=c;j1++)
		  m[n][j1]=v[n];
	  for(int i=n-1;i>1;i--)
	  {
           jMax=min(w[i]-1,c);
		   for(int j2=0;j2<=jMax;j2++)
			   m[i][j2]=m[i+1][j2];
		   for(int j3=w[i];j3<=c;j3++)
			   m[i][j3]=max(m[i+1][j3],m[i+1][j3-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[101][101],int *w,int c,int *x,int wlen)
{
	int n=wlen-1;
	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;
}