分支界限算法【0-1背包问题】按照优先队列式（LC）分支限界法求解0-1背包问题，并给出限界函数，并画出该实例的状态空间树。

末蓝、 2022-12-25 01:55 251阅读 0赞

***目   录***

回溯算法【0-1背包问题】

分支界限算法【0-1背包问题】

作业题（期末考试必考）

小结

--------------------

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70][]

# [回溯算法【0-1背包问题】][0-1] #

> ![20201130111429794.png][]

# 分支界限算法【0-1背包问题】 #

> ![20201130105115714.png][]
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 1][]

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 2][]

> **解决思路：****采用优先队列式分支限界**
> 
> Ø  **确定** **目标函数上、下界；**
> 
> Ø  **确定** **目标函数的计算方法；**
> 
> **一般情况下，****假设当前已对前*****i*****个物品进行了某种特定的选择，****且背包中已装入物品的重量是*****w，*****获得的价值是*****v，*****计算该结点的目标函数上界的一个简单方法是，将背包中剩余容量全部装入第*****i*****+1****个物品，****并可以将背包装满，****于是，****得到限界函数：**
> 
> ![ub = v + (W-w)\\times (v\_\{i+1\} / w\_\{i+1\})][ub _ v _ _W-w_times _v_i_1_ _ w_i_1]
> 
> Ø **依** **上计算从** **根结点到叶子结点的目标函数值** **直到** **表** **PT** **（待处理活结点列表）中** **取得极大值** **。**

> ![20201130104812907.png][]
> 
> ![20201224130535242.png][]

> **分支限界法求解****0/1****背包问题算法用伪代码描述如下**：
> 
> 算法7.1：分枝限界法求解0/1背包问题
> 
> 输入：n个物品的重量w\[n\]，价值v\[n\]，背包容量W
> 
> 输出：背包获得的最大价值和装入背包的物品
> 
> 1. 根据限界函数计算目标函数的上界up；采用贪心法得到下界down；
> 
> 2. 计算根结点的目标函数值并加入待处理结点表PT；
> 
> 3. 循环直到某个叶子结点的目标函数值在表PT中取极大值
> 
>    3.1  i = 表PT中具有最大值的结点；
> 
>    3.2 对结点i的每个孩子结点x执行下列操作：
> 
>          3.2.1 如果结点x不满足约束条件，则丢弃该结点；
> 
>          3.2.2 否则，估算结点x的目标函数值lb，
> 
>                   将结点x加入表PT中；
> 
> 4. 将叶子结点对应的最优值输出，回溯求得最优解的各个分量。

# 作业题（期末考试必考） #

> 按照优先队列式（LC）分支限界法求解0-1背包问题， 并给出限界函数，并画出该实例的状态空间树。
> 
> ![20201130105038365.png][]

> 老师讲解此题的板书：
> 
> ![20201130105357153.jpg][]
> 
> 博主课堂笔记（仅供参考）：
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 3][]
> 
> **背包容量下界的计算：**
> 
> 背包容量W=16。  
> ①放入物品1(w1=10;v1=100)和物品4(w4=4;v4=12)，背包物品总重量w=14，v=112；  
> ②放入物品2(w1=  7;v1=63  )和物品4(w4=4;v4=12)，背包物品总重量w=11，v= 75；  
> ③放入物品3(w1=  8;v1=56  )和物品4(w4=4;v4=12)，背包物品总重量w=12，v= 68。  
> 下界取最大值，即下界w=112。

# 小结 #

> 回溯算法和分支限界算法在最坏情况下需要遍历所有的节点，因此其最坏的算法时间效率也是指数级的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70]: /images/20221120/852c6fbe48894bb2afaa9400eaf6784a.png
[0-1]: https://blog.csdn.net/weixin_44949135/article/details/110382318
[20201130111429794.png]: /images/20221120/b3aa0f76902749c1b6fd866a6a2635d3.png
[20201130105115714.png]: /images/20221120/d10e230a5deb4844829786c8f161c121.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 1]: /images/20221120/c05aa76ad8d548b99d8733f1c071a462.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 2]: /images/20221120/df8f92494d63421a9bd4ffd1f5ff7687.png
[ub _ v _ _W-w_times _v_i_1_ _ w_i_1]: https://private.codecogs.com/gif.latex?ub%20%3D%20v%20&plus;%20%28W-w%29%5Ctimes%20%28v_%7Bi&plus;1%7D%20/%20w_%7Bi&plus;1%7D%29
[20201130104812907.png]: /images/20221120/75093937d78148d4b1d53ad107164f58.png
[20201224130535242.png]: /images/20221120/b1d68375fc934aa4a988c5f1b77ed04c.png
[20201130105038365.png]: /images/20221120/cdc47c57fef047879571d35736e3a164.png
[20201130105357153.jpg]: /images/20221120/a3d30c0d076246fab7de708fa8844973.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 3]: /images/20221120/be63e9756f3b40ae8596942067761030.png