e3.cpp

01背包问题题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包...但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维数组解01背

#include<iostream.h>
#include<iomanip.h>
#define length 5
int max(int a,int b)
{
	if(a>=b) return a;
	else return b;
}
int min(int a,int b)
{
	if(a<=b) return a;
	else return b;
}
void knapsack(int v[5],int w[5],int c,int m[5][11])
{
	int n=length-1;
	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>=0;i--)
	{
		jMax=min(w[i]-1,c);
		for(int j=0;j<=jMax;j++)
			m[i][j]=m[i+1][j];
		for(int k=w[i];k<=c;k++)
			m[i][k]=max(m[i+1][k],m[i+1][k-w[i]]+v[i]);
	}
}
void traceback(int m[5][11],int w[5],int c,int x[5])
{
	int n=length-1;
	for(int i=0;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 x[5]={0};
	int value[length]={6,3,5,4,6};
	int weight[length]={2,2,6,5,4};
	int c=10;
	int m[5][11]={0};
    knapsack(value,weight,10,m);
	for(int y=0;y<11;y++)
		cout<<setw(5)<<y;
	cout<<"   重量"<<"   价值"<<endl;
 	for(int i=0;i<5;i++)
	{
 		for(int j=0;j<11;j++)
 			cout<<setw(5)<<m[i][j];
 	    cout<<"     "<<weight[i]<<"     "<<value[i]<<endl;
	}
	traceback(m,weight,10,x);
   for(int k=0;k<5;k++)	
	cout<<x[k]<<endl;
}