动态规划--0-1背包问题.txt

使用C++编写的动态规划--0-1背包问题。

#include<iostream>
using namespace std;

typedef int Type;
void Knapsack(int v[],int w[],int c,int n,int (*m)[11]);
void Trackback(int (*m)[11],int w[],int c,int n,int x[]);
int max(int first,int second);
int min(int first,int second);
void main()
{
	cout<<"\t\t\t***********************************"<<endl;
	cout<<"\t\t\t       动态规划--0-1背包问题"<<endl;
	cout<<"\t\t\t     海川工作室出品(2007.5.11)"<<endl;
	cout<<"\t\t\t***********************************"<<endl;
	cout<<"设背包能够装进物体的总质量是10kg."<<endl;
	cout<<"一共有4件物品，4件物品的重量分别是:0,2,3,4,5kg."<<endl;
	cout<<"4件物品的价值分别是0,7,8,9,10"<<endl;
	int PackWeight=10;											//设定背包总共能够装下物品的重量
    int ObjectWeight[5]={0,2,3,4,5};							//物品的重量依次是(0号空间不算)
	int ObjectValue[5]={0,7,8,9,10};							//物品的价值依次是(0号空间不算)
	int Whether[5];
	int plan[5][11];
	for(unsigned short horizontal=1;horizontal<5;horizontal++)
	{
		for(unsigned short vertical=1;vertical<=10;vertical++)
		{
			plan[horizontal][vertical]=0;
		}
	}
	Knapsack(ObjectValue,ObjectWeight,PackWeight,4,plan);
	Trackback(plan,ObjectWeight,PackWeight,4,Whether);
	for(horizontal=1;horizontal<5;horizontal++)
	{
		for(unsigned short vertical=1;vertical<=10;vertical++)
		{
			cout<<plan[horizontal][vertical]<<'\t';
		}
		cout<<endl;
	}
	for(unsigned short place=1;place<=4;place++)
	{
		cout<<Whether[place]<<"\t";
	}
}
void Knapsack(int v[],int w[],int c,int n,int (*m)[11])
{
	// p72
	int jMax=min(w[n]-1,c);
	for(int j=0;j<=jMax;j++)
	{
		m[n][j]=0;  
	}
	for(j=w[n];j<=c;j++)
	{
		m[n][j]=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(j=w[i];j<=c;j++)
		{
			m[i][j]=max(m[i+1][j],m[i+1][j-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 Trackback(int (*m)[11],int w[],int c,int n,int x[])
{
	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;
	  }
}

int max(int first,int second)
{
	if(first>second)
	{
		return first;
	}
	else
	{
		return second;
	}
}
int min(int first,int second)
{
	if(first<second)
	{
		return first;
	}
	else
	{
		return second;
	}
}