fuliang 发表于 2013-2-5 01:21:51

回溯法之三--0-1背包问题

0-1背包问题:给定n种物品和一背包.物品i的重量是wi, 其价值为ui,背包的容量为C.
问如何选择装入背包的物品,使得装入背包中物品的总价值最大?
分析:
0-1背包是子集合选取问题,一般情况下0-1背包是个NP问题.
第一步 确定解空间:装入哪几种物品
第二步 确定易于搜索的解空间结构:
可以用数组p,w分别表示各个物品价值和重量。
用数组x记录,是否选种物品
第三步 以深度优先的方式搜索解空间,并在搜索的过程中剪枝
我们同样可以使用子集合问题的框架来写我们的代码,和前面子集和数问题相差无几。
#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;   cx = new int;}void knapsack(){   backtrack(0); }void backtrack(int i){//回溯法if(i > n){    if(cp > bestp){       bestp = cp;       for(int i = 0; i < n; i++) x = cx;    }    return;}if(cw + w <= c){//搜索右子树cw += w;cp += p;cx = 1;backtrack(i+1);cw -= w;cp -= p;}cx = 0;backtrack(i+1);//搜索左子树}void printResult(){   cout << "可以装入的最大价值为:" << bestp << endl;   cout << "装入的物品依次为:";   for(int i = 0; i < n; i++){   if(x == 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 = {9,10,7,4},w = {3,5,2,1};    Knapsack ks = Knapsack(p,w,4,7);    ks.knapsack();  ks.printResult();  return 0;}
页: [1]
查看完整版本: 回溯法之三--0-1背包问题