算法设计与分析 课件 8.1-分支限界 - 引例 - 0-1背包问题.pptx

算法设计与分析

分支限界引例

国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版

有n个可选择物品的0-1背包问题

解题方法：

穷举法

动态规划法

回溯法：深度优先搜索

其他方法？

----广度优先搜索

思考的要点：解空间树及广度优先搜索

A

C

B

A

E

C

B

F

E

C

G

OK!

P=45

G

F

E

OK!

P=45

OK!

P=50

OK!

P=25

G

F

OK!

P=45

OK!

P=50

OK!

P=25

OK!

P=25

OK!

P=0

G

OK!

P=45

OK!

P=50

OK!

P=25

OK!

P=25

OK!

P=0

只有分支的搜索，其实就是穷举法

分支限界=分支+限界

测试

选择题：

本节所讲的0-1背包问题的求解过程中，使用的搜索策略是（）

A：深度优先搜索

B：广度优先搜索

C：随机搜索