// PackProblemClass.h: interface for the PackProblemClass class.////////////////////////////////////////////////////////////////////////#if !defined(AFX_PACKPROBLEMCLASS_H__60EB89B2_4A0F_4085_8973_AC42DE6842E5__INCLUDED_)#define AFX_PACKPROBLEMCLASS_H__60EB89B2_4A0F_4085_8973_AC42DE6842E5__INCLUDED_#if _MSC_VER > 1000#pragma once#endif // _MSC_VER > 1000class PackProblemClass  {public:	int S;//背包的容量为S	int N;//物品的件数为N	int *w;//物品的重量 N维数组	int *v;//物品的价值 N维数组	int *x;//背包装的物品价值最大时对应的物品种类 N维数组 x[i]=1表示第i个物品在背包中	int V;//背包能装下的最大价值	void DynamicProgramming();//进行动态规划，计算最大价值V，和对应的物品组合x	void ResultOutput();//将动态规划结果输出	PackProblemClass(int iS,int iN,int *iw,int *iv);//构造函数	virtual ~PackProblemClass();//析构函数	};#endif // !defined(AFX_PACKPROBLEMCLASS_H__60EB89B2_4A0F_4085_8973_AC42DE6842E5__INCLUDED_)

// PackProblemClass.cpp: implementation of the PackProblemClass class.////////////////////////////////////////////////////////////////////////#include "stdafx.h"#include "PackProblemClass.h"#include <iostream>using namespace std;//////////////////////////////////////////////////////////////////////// Construction/Destruction////////////////////////////////////////////////////////////////////////背包问题类PackProblemClass::PackProblemClass(int iS,int iN,int *iw,int *iv){	this->S = iS;//背包的容量为S	this->N = iN;//物品的件数为N	this->w = iw;//物品的重量 N维数组	this->v = iv;//物品的价值 N维数组	this->V = 0;//背包能装下的最大价值	this->x = new int[N];//背包装的物品价值最大时对应的物品种类 N维数组 x[i]=1表示第i个物品在背包中	for(int i=0;i<N;i++)//初始化x	{		x[i] = 0;	}}void PackProblemClass::DynamicProgramming()//进行动态规划，计算最大价值V，和对应的物品组合x{	int temp_S = S + 1;	int i,j; 	//动态定义并初始化二维数组	int **c;	c = new int*[N+1];	for(i=0;i<=N;i++)	{		c[i] = new int[temp_S];	}	for(i=0;i<=N;i++)	{		for(j=0;j<=S;j++)		{			c[i][j] = 0;		}	}	//////////////////////////	//根据公式c[i][j]=MAX{c[i-1][j]，c[i-1][j-w[i-1]+v[i-1]]}计算c[][]	for(i=1;i<=N;i++)	{		for(j=1;j<=S;j++)		{			if (j>=w[i-1]) {				if (c[i-1][j]<(c[i-1][j-w[i-1]]+v[i-1])) {					c[i][j] = c[i-1][j-w[i-1]]+v[i-1];				}else				{					c[i][j] = c[i-1][j];				}			}else			{				c[i][j] = c[i-1][j];			}		}	}	//输出c[][]	for(i=0;i<=N;i++)	{		for(j=0;j<=S;j++)		{			cout<<c[i][j]<<"  ";		}		cout<<endl;	}	/////////////////////////////////////////////////////////////	//逆推法计算最大值V时对应的物品组合x	V = c[N][S];	temp_S = S;	for(i=N;i>0;i--)	{		if (c[i][temp_S]>c[i-1][temp_S]) {			x[i-1] = 1;			temp_S = temp_S - w[i-1];		}	}}void PackProblemClass::ResultOutput()//将动态规划结果输出{	cout<<"背包的容量:"<<S<<endl;	cout<<"物品的件数:"<<N<<endl;	cout<<"物品的重量:"<<endl;	int i;	for(i=0;i<N;i++)		cout<<w[i]<<" "<<endl;	cout<<endl;	cout<<"物品的价值:"<<endl;	for(i=0;i<N;i++)		cout<<v[i]<<" "<<endl;	cout<<endl;	cout<<"动态规划的结果为:"<<endl;	cout<<"背包所能装下的物品的最大价值为:"<<V<<endl;	cout<<"物品的种类:"<<endl;	for(i=0;i<N;i++)		cout<<x[i]<<" "<<w[i]<<" "<<v[i]<<endl;	cout<<endl;}PackProblemClass::~PackProblemClass(){}