遡及法の3--0-1リュックサック問題

0-1リュックサックの問題:n種類の物品とリュックサックを与えた.物品iの重量はwiである、その価値はuiであり、リュックサックの容量はCである.
リュックサックに入れたものをどのように選んで、リュックサックに入れたものの総価値を最大にしますか?
分析:
0-1バックパックはサブセットの選択問題であり、一般的に0-1バックパックはNP問題である.
第1歩は解空間を確定します:どの何種類の物品を入れます
2番目のステップでは、検索しやすい解空間構造を決定します.
配列p,wでそれぞれの物品価値と重量を表すことができる.
配列xで記録し、アイテムを選択するかどうか
ステップ3では、深さ優先で解空間を検索し、検索中に枝を切ります.
サブセット問題のフレームワークを使用してコードを書くこともできます.前のサブセットと数の問題とほとんど変わりません.

#include<iostream>
#include<algorithm>
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;
}