限界算法求解-1背包问题的便利和实验环境操作系统

1.掌握使用分支定界算法解决0-1背包问题的原理以及编写分支定界函数的具体步骤。

2.掌握分支定界法的基本思想，通过解决0-1背包问题体验使用优先级队列分支定界的方法，从而了解分支定界算法的基本求解过程。

3.了解分支定界算法解决问题的便利性以及编写的程序结构清晰、可读性好。

4.有能力运用分支定界算法的思想来设计算法并用其解决其他实际应用问题。

5、从算法设计分析的角度，比较学习分支定界法解决问题和回溯法解决问题的不同思路，从而对基于0-1背包问题的解决有更进一步的理解关于分支定界法。

2. 实验环境

操作系统：10

文本编辑器：代码

实验语言和编译器：C++

编译器：gcc 8.1.0

实验终端：

三、实验内容

现在给定N件物品，每件物品的重量为w（即物品i的重量为wi），给定一个背包，背包的容量为c，要解决的0-1背包问题是装载它通过选择 中的物品放入背包中，使所选物品的重量w之和小于或等于背包的容量，这样装入背包的物品的价值是所有选择中最大的。

0-1背包问题有以下限制。 对于每一项i，有两个选项，加载或不加载（加载为1，不加载为0）。 不能多次加载，也不能只加载。 加载部分。

W(重量)

P（值）

10

例如，当前背包容量为9，有4个物品，每个物品的重量和价值如上图所示：通过分析可以看出，最优方案是装载有价值的物品​​​​9,10,4，最优值为23，下面将通过回溯算法解决01背包问题。

程序输入，首先输入物品数量n和背包容量c，然后依次输入n件物品的重量wi和每件物品的值pi。 程序要求输出是可以获得的最优值以及达到最优值的负载。 商品序列号。

4. 算法说明

通过分析问题可以看出，0-1背包问题是整数线性规划中的01规划问题。

对于回溯算法来说，这n个物品被加载到背包中，每个物品对应两种状态，加载到背包中或未加载到背包中。 第i个物品对应(x1,x2,...,xn)，其中xi可以是0或1，表示是否将该物品放入背包中。 解空间中有2^n种可能的解，它是由n个元素组成的集合的所有子集的数量。 该集合可以使用完整二叉树来组织。 解空间的深度就是问题n的大小。 。

使用优先级队列分支定界法解决0-1背包问题搜索解空间的策略是，首先在扩展节点（对应代码中的E）生成其所有子节点（分支），然后从当前优先级队列中选择下一个扩展节点。 为了加快搜索过程，首先在每个存活节点计算一个函数值（bound，使用Bound函数实现），并根据该函数值从优先级队列中选择最优节点作为扩展。 节点使搜索向解空间中具有最优解的分支移动，提高了搜索速度。

在优先级队列的实现中，项目由结构体obj表示。 结构体中的成员p表示物品的价值，成员w表示物品的重量，成员pDivW表示物品的单位价值。

算法从根节点开始搜索。 最初，优先级队列为空（最大堆为空）。 取出优先级队列中的第一个元素成为当前扩展节点E，并将扩展节点的左右儿子设为可行节点，添加到优先级队列中，优先级中节点元素的优先级队列是通过Bound函数计算的。 节点元素由结构节点表示。 节点元素中使用up表示该节点值的上限，表示该节点对应的值和权重，使用变量level表示该节点元素在子集树中对应的层数，使用节点指针指向子集树中该节点的父节点。

在寻找最优解的过程中，可以利用剪枝函数来加快搜索速度。 界函数给出了每个可行节点对应的子树可能获得的最大值的上界。 如果这个上界不大于当前最优值，则可以对该分支进行剪枝（因为对应的子树不包含问题的最优解）。

在开始搜索之前，()使用sort对obj结构体数组objs按单位值非递增排序。 E表示当前扩展节点，cw是扩展节点对应的权重，cp对应该节点的值，up表示当前值上界。 搜索过程如下：

①：初始化优先级队列q（在stl中实现，优先级队列排序是使用函子实现的），展开节点E，初始化变量cw，cp为0。

②：将当前最优值bestp赋值为0，上界up的值为Bound(1)。

③：在while循环内部不断扩展节点，直到子集树的叶子节点成为扩展节点。 首先，确定当前扩展节点的左子节点。 如果左子节点是可行节点，则调用左子节点并将其添加到优先级队列中。

④：将up值更新为Bound(i+1)，并检查当前扩展节点的右子节点。 如果up≥bestp，则意味着右子树可能包含最优解，调用会将右子节点添加到优先级队列中。

⑤：从优先级队列中移除一个节点，继续循环。 循环结束后，构造当前最优解。

代码逻辑如下：

, cmp > q; // 大顶堆

节点 *E = NULL;

CW = 0;

cp = 0;

最佳p = 0;

整数 i = 1;

int up = Bound(1);

//搜索子集空间树

而（我！= n + 1）

//检查当前扩展节点的左儿子

int wt = CW + objs[i].w;

//如果左子节点是可行节点

if(wt = 最佳p)

(q, E, 向上, CW, cp, i, 0);

E = ();

q.pop();

CW = E->;

cp = E->;

向上 = E->向上；

i = E->级别；

for(int j = n; j > 0; j--)

bestx[objs[E->level - 1].id] = E->lc;

E = E->;

该函数将一个新的活动节点插入到优先级队列中。 该函数仅完成新节点的初始化。

算法时间复杂度分析，分支定界法的时间复杂度取决于定界函数的时间复杂度，为O(n2^n)。

5. 实验结果

第一组输入，假设有4件物品，它们的权重为(4,7,5,3)，它们的值为(40,42,25,12)，背包容量为10，最优值为通过程序获取到的数据为65，需要加载的item为Item 1和Item 3。

第二组和第三组输入均假设有 4 个项目。 第二组输入物品的重量为(2,4,6,8)，背包容量为999，通过程序计算出的最优值为20，可以装入所有物品。 第三组输入物品的重量为(10,11,12,13)​​，背包容量为10。通过程序得到的最优值为5，即装载第一个物品。

6. 实验总结

对于0-1背包问题，分别通过动态规划算法、回溯算法和分支定界法进行求解，时间复杂度分别为O(nc)、O(n2^n)、O(n2^n)。 动态规划时，通过寻找最优子结构将整个问题的解转换为子问题的解，并在转换过程中判断是否应该选择特定的乘积。

回溯法利用贪心性质（按单位权重值降序排序，估计可能的最高上限）对整个解空间进行搜索，并将计算出的可行解作为剪枝的极限，减少了大量的计算量。

在优先级队列分支定界法中，剪枝过程与回溯法相同，利用贪心性质（按单位权重值降序排序，估计最大可能的上界）和计算出的可行解作为极限修剪。 不同之处在于分支定界方法使用优先级队列。 当一个节点展开时，所有子节点都会展开，并计算所有子节点所能达到的最高上限。 当优先级队列中的第一个节点是可行解决方案时，它结束。

也就是说，回溯法与分支定界法的本质区别在于搜索解空间的遍历方法不同。 回溯法是一种深度优先搜索，穷尽解空间中的所有可能性（尽管也进行了剪枝）来寻找最优解。 分支定界法是一种广度优先搜索，它也会穷尽解空间中的所有可能性来寻找最优解。

通过比较和学习解决0-1背包问题的三种算法，加深了对动态规划、回溯算法和分支定界法的理解。 经过对这些算法的比较和研究，我意识到算法的本质不在于它的方法，而在于算法的思想。 掌握算法的思维，可以潜移默化地解决很多问题。