e3.txt

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

#include<iostream.h>
#include<iomanip.h>
#define length 4
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[4],int w[4],int c,int m[4][10])
{
	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[1]-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]);
	}
	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[4][10],int w[4],int c,int x[4])
{
	int n=length-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;
}

void main()
{
	int x[4]={0};
	int value[length]={5,4,6,3};
	int weight[length]={4,3,5,3};
	int c=10;
	int m[4][10]={0};
    knapsack(value,weight,10,m);
 	for(int i=0;i<4;i++)
	{
 		for(int j=0;j<10;j++)
 			cout<<setw(4)<<m[i][j];
 	    cout<<endl;
	}
	traceback(m,weight,10,x);
   for(int k=0;k<4;k++)	
	cout<<x[k]<<endl;
}