资源描述：
《算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第7章）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第7章回溯和分支限界基本思想0-1背包问题旅行商问题其它若干典型问题7.1回溯和分支限界法的基本思想状态空间:问题（实例）的所有可能解0-1背包问题:{0,1}n旅行商问题:perms(V)7.1回溯和分支限界法的基本思想状态空间:问题（实例）的所有可能解穷举法:搜索整个状态空间0-1背包问题:{0,1}n旅行商问题:perms(V)O(n2n)O(n!)7.1回溯和分支限界法的基本思想状态空间:问题（实例）的所有可能解穷举法:搜索整个状态空间高效算法:缩小搜索空间(放弃无用的那部分状态空间)0-1背包问题:{0,1}n旅行商问题:perms(V)O(n2n)
2、O(n!)剪枝7.1回溯和分支限界法的基本思想剪枝约束函数:除去违反约束条件的解限界函数:放弃不可能达到最优解的路径7.1回溯和分支限界法的基本思想搜索策略深度优先:回溯广度优先:分支限界7.20-1背包问题输入：n件物品的集合S(其中第i件物品的重量和价值分别为S[i].w和S[i].v)，以及背包的最大承重量W输出：S的一个子集A，其重量之和不大于W，且价值之和最大wvS:(3,8)(20,50)(5,12)(10,21)(5,10)W=307.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58第1个可行解:11100
3、(70)12,7002,7002,70wvS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:58+21+10=897.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58第1个可行解:11100(70)12,7002,7002,70wvS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:58+10=6807,587.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58第1个可行解:11100(70)1
4、2,7002,7002,70wvS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:8+12+21+10=5107,58027,87.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58第1个可行解:11100(70)12,7002,7002,70wvS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:50+12+21+10=9307,58027,8030,07.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,
5、817,58第1个可行解:11100(70)12,7002,7002,70wvS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:50+12+21+10=9307,58027,8030,0110,5015,627.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58第1个可行解:11100(70)12,7002,7002,70wvS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:62+10=7207,58027,8030,0110,50
6、15,6205,627.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58当前最优解:01101(72)12,7002,7002,70wvS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,5807,58027,8030,0110,5015,6205,6210,727.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58当前最优解:01101(72)12,7002,7002,70wvS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007
7、,58bound:50+21+10=8107,58027,8030,0110,5015,6205,6210,72010,5010,717.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58当前最优解:01101(72)12,7002,7002,70wvS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:50+10=6007,58027,8030,0110,5015,6205,6210,72010,5010,7100,71010,507.20-1背包问题限界函数：当前背包价值加上剩
8、余所有物品的价值30,0127,817
