01knapsack.cpp

01背包问题的C++源程序

#include<iomanip>
#include <iostream> 
#include <string> 

using namespace std; 

int min(int w,int c)
{
	int temp;
	if (w<c) 
		temp=w;
	else
		temp=c;
 return temp;
}

int max(int w,int c)
{
	int temp;
	if (w>c) 
		temp=w;
	else
		temp=c;
	return temp;
}


void knapsack(int v[],int w[],int c,int n,int**m)      //求最优值
{
	int jmax=min(w[n]-1,c);
	for(int j=0;j<=jmax;j++)
		m[n][j]=0;
	for(int jj=w[n];jj<=c;jj++)
		m[n][jj]=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 jj=w[i];jj<=c;jj++)
			m[i][jj]=max(m[i+1][jj],m[i+1][jj-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]);
	
	//cout<<"最优值："<<m[1][c]<<endl;
	//for(int l=2;l<=n;l++)
	//	for(int j=0;j<=c;j++)
	//	{
	//		cout<<m[l][j]<<setw(c-1);
	//	}    
	//cout<<endl;
	//cout<<"*******************************************"<<endl;
}

int traceback(int **m,int w[],int c,int n,int x[])      //回代，求最优解
{
	cout<<"得到的一组最优解如下:"<<endl;
	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])?1:0;
	for(int y=1;y<=n;y++)
	{
		cout<<setw(5)<<x[y];
	}
	return x[n];
}

void main()
{
	int n,c;
	int **m;
	cout<<"&&&&&&&&&&&&&&&&&&&&&欢迎使用0-1背包问题程序&&&&&&&&&&&&&&&&&&&"<<endl;
	cout<<"请输入物品个数和重量上限:";
	cin>>n>>c;
	int *v=new int[n+1];
	cout<<"Pls input the property (v[i]):"<<endl;
	for(int i=1;i<=n;i++)
		cin>>v[i];
	int *w=new int[n+1];
	cout<<"Pls input the weight (w[i]):"<<endl;
	for(int j=1;j<=n;j++)
		cin>>w[j];
	int *x=new int[n+1];
	m=new int*[n+1];  //动态的分配二维数组
	for(int p=0;p<n+1;p++)
	{
		m[p]=new int[c+1];
	} 

	knapsack(v,w,c,n,m);
	traceback(m,w,c,n,x);
	cin >>c;
}