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

一维数组，即回溯法求解0/1背包问题的空间复杂度为O(n)。

4.分支限界法求解背包问题：

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

struct KNAPNODE //状态结构体

{

bool s1[N]; //当前放入物体

int k; //搜索深度

int b; //价值上界

int w; //物体重量