C++回溯法解决背包问题源码演示

工作之余，把代码过程常用的内容做个备份，下面代码段是关于C++回溯法解决背包问题演示的代码，应该对各位有较大好处。

#include<iostream>

#include<algorithm>

using namespace std;

class Knapsack{

public:

  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);

}

if(i > n){

    if(cp > bestp){

      bestp = cp;

      for(int i = 0; i < n; i++)

x[i] = cx[i];

    }

    return;

}

  cw += w[i];

  cp += p[i];

  cx[i] = 1;

  backtrack(i+1);

  cw -= w[i];

  cp -= p[i];

}

cx[i] = 0;

}

void printResult(){

  cout << "可以装入的最大价值为:" << bestp << endl;

  cout << "装入的物品依次为:";

  for(int i = 0; i < n; i++){

    if(x[i] == 1)

cout << i+1 << " ";

  }

  cout << endl;

}

private:

  int n;

  double c;

};

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;

}