算法分析之 0_1背包问题回溯法

用回溯法解0_1背包问题时，会用到状态空间树。在搜索状态空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索，否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r≤bestp时，可剪去右子树。计算右子树中解的上界可以用的方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界，用此值来剪枝。 为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要顺序考察各物品即可。在实现时，由MaxBoundary函数计算当

#include

using namespace std;
 
 
class Knap
{
	friend int Knapsack（int p[]int w[]int cint n ）;
 
public:
	void print（）
	{
    	for（int m=1;m<=n;m++）
		 {
			if（m%10==0） printf（“\n“）;
			printf（“%-4d“bestx[m]）;
		 }
		printf（“\n“）;
	 };
 
private:
  int Bound（int i）;
  void Backtrack（int i）;
 
  int c;//背包容量
  int n; //物品数
  int *w;//物品重量数组
  int *p;//物品价值数组
  int cw;//当前重量
  int cp;//当前价值
  int bestp;//当前最优值
  int *bestx;//当前最优解
  int *x;//当前解
 
};
 
// ************** Bound（） 计算上界 ********************************
int Knap::Bound（int i） 
{
 int cleft=c-cw;//剩余容量
 int b=cp;
 //以物品单位重量价值递减序装入物品
 while（i<=n&&w[i]<=cleft）
 {
   cleft-=w[i];
   b+=p[i];
   i++;
 }
 //装满背包
 if（i<=n）
  b+=p[i]/w[i]*cleft;
 return b;
}
 
// *****

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2012-12-04 22:40  0_1背包回溯法\
     文件        2861  2012-12-04 22:38  0_1背包回溯法\0_1背包回溯法.cpp
     文件        3487  2012-12-04 14:59  0_1背包回溯法\0_1背包回溯法.dsp
     文件         551  2012-12-04 22:38  0_1背包回溯法\0_1背包回溯法.dsw
     文件       41984  2012-12-04 22:38  0_1背包回溯法\0_1背包回溯法.ncb
     文件       48640  2012-12-04 22:38  0_1背包回溯法\0_1背包回溯法.opt
     文件         773  2012-12-04 22:38  0_1背包回溯法\0_1背包回溯法.plg
     目录           0  2012-12-04 22:40  0_1背包回溯法\Debug\
     文件      548970  2012-12-04 22:38  0_1背包回溯法\Debug\0_1背包回溯法.exe
     文件      788892  2012-12-04 22:38  0_1背包回溯法\Debug\0_1背包回溯法.ilk
     文件      253772  2012-12-04 22:38  0_1背包回溯法\Debug\0_1背包回溯法.obj
     文件     1997944  2012-12-04 14:59  0_1背包回溯法\Debug\0_1背包回溯法.pch
     文件     1098752  2012-12-04 22:38  0_1背包回溯法\Debug\0_1背包回溯法.pdb
     文件       74752  2012-12-04 22:38  0_1背包回溯法\Debug\vc60.idb
     文件      110592  2012-12-04 22:38  0_1背包回溯法\Debug\vc60.pdb