回溯法求背包问题

#include<iostream>
#define N 3 //物品总数
#define C 16//背包总质量
using namespace std;
int w[N]={10,8,5};  //每个物品的重量
int v[N]={5,4,1};   //每个物品的价值
int x[N]={0,0,0};   //x[i]=1代表物品i放入背包，0代表不放入
int CurWeight = 0;  //当前放入背包的物品总重量
int CurValue = 0;   //当前放入背包的物品总价值
int BestValue = 0;  //最优值；当前的最大价值，初始化为0
int BestX[N];       //最优解；BestX[i]=1代表物品i放入背包，0代表不放入
void backtrack(int t){
  if(t>N-1){
    if(CurValue>BestValue){
      BestValue=CurValue;//更新最优解
      for(int i=0;i<N;i++){
        BestX[i]=x[i];//将最优解的记录记入最优解中
      }
    }
  }
  else
  for(int i=0;i<=1;i++){
    x[t]=i;
    if(i==0){//不放入背包
      backtrack(t+1);
    }
    else{//放入背包进行判断
      if(CurWeight+w[t]<=C){
        CurWeight+=w[t];
        CurValue+=v[t];
        x[t]=1;//放入背包记为1
        backtrack(t+1);//放入后进行递归，对后面的影响
        CurValue-=v[t];
        CurWeight-=w[t];
        x[t]=0;//取出来记为0，
        backtrack(t+1);//不放入对后面的影响
      }
    }
  }
}
int main(int argc, char const *argv[]) {
  backtrack(0);
  cout<<BestValue<<endl;
  for(int i=0;i<N;i++){
    cout<<BestX[i]<<" ";
  }
  return 0;
}