0-1背包问题回溯算法

这是以前在学校学算法设计时写的程序了，都不太记得了。 是0-1背包的回溯算法。 内附实验报告，详解算法设计过程。

//by ngl

#include
#include
using namespace std;

#define max 100
double c;	//背包容量
int n;		//物品数
double weight[ max ];		//物品重量数组
double value[ max ];		//物品价值数组
int a[max];                 //a[i]表示：排序前的物品i是排序后的物品a[i]
double v[max];              //按物品重量价值从大到小排序后的物品价值数组
double w[max];				//按物品重量价值从大到小排序后的物品重量数组
double cw = 0;				//当前重量
double cv = 0;				//当前价值
double bestp = 0;			//当前最优价值
int x[max];					//当前解
int bestx[max];				//当前最优解


//类Knapsack中存储物品编号和其对应的单位重量价值
class Knapsack
{
public:
	
	Knapsack（int idd = 0double dd = 0）
	{
		id = idd; 
		d = dd;   
	}

	bool equles（Knapsack x）
	{
		return d == x.d;
	}

	int id;   //物品编号
	double d; //物品单位重量价值

};

double bound（int i）//计算当前节点的上界
{
	double cleft = c - cw; //剩余容量
	double

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件    1189888  2010-12-15 18:45  0 1背包（回溯算法）\0 1背包（回溯算法）.doc

    ..A..H.      8192  2010-12-15 18:51  0 1背包（回溯算法）\0 1背包（回溯算法）.suo

     文件       1275  2010-12-15 18:48  0 1背包（回溯算法）\程序\0 1背包（回溯算法）.plg

     文件        919  2010-12-15 18:49  0 1背包（回溯算法）\程序\0 1背包（回溯算法）.sln

     文件       4997  2010-12-15 18:49  0 1背包（回溯算法）\程序\0 1背包（回溯算法）.vcproj

     文件       1427  2010-12-15 18:51  0 1背包（回溯算法）\程序\0 1背包（回溯算法）.vcproj.24E929573AE54B4.Administrator.user

     文件       3022  2010-12-15 18:50  0 1背包（回溯算法）\程序\0 1背包（回溯算法）.cpp

     文件       3559  2010-12-15 18:48  0 1背包（回溯算法）\程序\0 1背包（回溯算法）.dsp

     文件        563  2010-12-15 18:49  0 1背包（回溯算法）\程序\0 1背包（回溯算法）.dsw

     文件    1346560  2010-12-15 18:51  0 1背包（回溯算法）\程序\0 1背包（回溯算法）.ncb

     文件      48640  2010-12-15 18:49  0 1背包（回溯算法）\程序\0 1背包（回溯算法）.opt

     目录          0  2010-12-15 18:53  0 1背包（回溯算法）\程序

     目录          0  2010-12-15 18:51  0 1背包（回溯算法）

----------- ---------  ---------- -----  ----

              2609042                    13