蛮力法、动态规划法、回溯法和分支限界法求解(5)

地利用限界函数(bounding function)来处死那些实际上不可能产生所

需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生

成法称为回溯法。

对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1

向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一

个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进

入右子树搜索。

2）代码:

#include<iostream>

#include<algorithm>

using namespace std;

#define N 100 //最多可能物体数

struct goods //物品结构体

{

int sign; //物品序号 int w; //物品重量

int p; //物品价值

}a[N];

bool m(goods a,goods b)

{

return (a.p/a.w)>(b.p/b.w);

}

int max(int a,int b)

{

return a<b?b:a;

}

int n,C,bestP=0,cp=0,cw=0;

int X[N],cx[N];

int BackTrack(int i)

{

if(i>n-1){ if(bestP<cp){ for (int k=0;k<n;k++) bestP=cp; X[k]=cx[k];//存储最优路径 } return bestP; //进入左子树 } if(cw+a[i].w<=C){ cw=cw+a[i].w; cp=cp+a[i].p; cx[a[i].sign]=1; //装入背包 BackTrack(i+1); cw=cw-a[i].w; cp=cp-a[i].p; //回溯，进入右子树