C++回溯法解决背包问题代码示范

0-1背包问题:给定n种物品和一背包.物品i的重量是wi, 其价值为ui,背包的容量为C. 问如何选择装入背包的物品,使得装入背包中物品的总价值最大? 分析: 0-1背包是子集合选取问题,一般情况下0-1背包是个NP问题. 第一步　确定解空间：装入哪几种物品 第二步　确定易于搜索的解空间结构： 可以用数组p,w分别表示各个物品价值和重量。 用数组x记录，是否选种物品 第三步　以深度优先的方式搜索解空间，并在搜索的过程中剪枝 我们同样可以使用子集合问题的框架来写我们的代码，和前面子集和数问题相差无几。 转自：http://fuliang.iteye.com/blog/165308/

#include
#include
using namespace std;
class Knapsack{
public:
	Knapsack(double *pp,double *ww,int nn,double cc){
	   p = pp;
	   w = ww;
	   n = nn;
	   c = cc;
	   cw = 0;
	   cp = 0;
	   bestp = 0;
	   x = new int[n];
	   cx = new int[n];
	}
	void knapsack(){
	   backtrack(0);
	 }
	void backtrack(int i){//回溯法
		if(i > n){
		    if(cp > bestp){
		       bestp = cp;
		       for(int i = 0; i < n; i++)
			 x[i] = cx[i];
		    }
		    return;
		}
		if(cw + w[i] <= c){//搜索右子树
		  cw += w[i];
		  cp += p[i];
		  cx[i] = 1;
		  backtrack(i+1);
		  cw -= w[i];
		  cp -= p[i];
		}
		cx[i] = 0;
		backtrack(i+1);//搜索左子树
	}
	void printResult(){
	   cout << "可以装入的最大价值为:" << bestp << endl;
	   cout << "装入的物品依次为:";
	   for(int i = 0; i < n; i++){
	     if(x[i] == 1)
			 cout << i+1 << " ";
	   }
	   cout << endl;
	}
private:
   double *p,*w;
   int n;
   double c;
   double bestp,cp,cw;//最大价值，当前价值，当前重量
   int *x,*cx;
};
int main(){
　　double p[4] = {9,10,7,4},w[4] = {3,5,2,1};
    Knapsack ks = Knapsack(p,w,4,7);
    ks.knapsack();
　　ks.printResult();
　　return 0;
}