背包问题回溯法

第二章 习题与解答

一 判断题

1．线性表的逻辑顺序与存储顺序总是一致的。

2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二 单选题 (请从下列A，B，C，D选项中选择一项)

1．线性表是( ) 。

(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空；

(C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ ）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n

3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的； (B) 部分地址必须是连续的；

(C) 一定是不连续的； (D) 连续与否均可以。

4．用链表表示线性表的优点是（ ）。

(A)便于随机存取

(B)花费的存储空间较顺序存储少

(C)便于插入和删除

(D)数据元素的物理顺序与逻辑顺序相同

5． 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

分⽀限界法解决01背包问题

分⽀限界法和之前讲的回溯法有⼀点相似，两者都是在问题的解的空间上搜索问题的解。但是两者还是有⼀些区别的，回溯法是求解在

解的空间中的满⾜的所有解，分⽀限界法则是求解⼀个最⼤解或最⼩解。这样，两者在解这⼀⽅⾯还是有⼀些不同的。之前回溯法讲了N后

问题，这个问题也是对于这有多个解，但是今天讲的01背包问题是只有⼀个解的。下⾯就讲讲分⽀限界法的基本思想。

分⽀限界法常以⼴度优先或以最⼩消耗（最⼤效益）优先的⽅式搜索问题的解空间树。问题的解空间树是表⽰问题解空间的⼀颗有序

树，常见的有⼦集树和排列树。分⽀限界法和回溯法的区别还有⼀点，它们对于当前扩展结点所采⽤的扩展⽅式也是不相同的。分⽀限界法

中，对于每⼀个活结点只有⼀次机会成为扩展结点。活结点⼀旦成为了扩展结点，就⼀次性产⽣其所有的⼦结点，⼦结点中，不符合要求的

和⾮最优解的⼦结点将会被舍弃，剩下的⼦结点将加⼊到活结点表中。再重复上⾯的过程，直到没有活结点表中没有结点，⾄此完成解决问

题的⽬的。

分⽀限界法⼤致的思想就是上⾯的叙述，现在就可以发现，对于结点的扩展将会成为分⽀限界法的主要核⼼。所以，分⽀限界法常见的

有两种扩展结点的⽅式，1.队列式（FIFO）分⽀限界法，2.优先队列式分⽀限界法。两种⽅法的区别就是对于活结点表中的取出结点的⽅式

不同，第⼀种⽅法是先进先出的⽅式，第⼆种是按优先级取出结点的⽅式。两中⽅法的区别下⾯也会提到。

在背包问题中还会提到⼀个⼦树上界的概念，其实就是回溯法中的剪枝函数，只不过，分⽀限界法⾥的剪枝函数改进了⼀些，剪枝函数

同样也是分⽀限界法⾥⽐较重要的东西。

下⾯就讲⼀讲01背包问题的实现。01背包问题和前⾯讲的背包问题的区别不⼤，就是01背包问题的物品不可以只放⼊部分，01背包问

题的物品只能放⼊和不放⼊两个选择，这也是名字中01的原因。其他的和背包问题相差不⼤，这⾥也不再累述。

算法的主体是⽐较容易想的，⾸先，将数据进⾏处理，这也是上⾯讲到的第⼆种取结点的⽅式（优先队列式）。因为要给每个物品设置优先

第１２卷第８期　２０１３年８，ｑ　软件导刊　Ｓｏｆｔｗａｒｅ　Ｇｕｉｄｅ　Ｖ＿０１．１２ＮＯ．８　Ａｕｇ．２Ｏ１３　

求解０—１背包问题算法研究　

王梦竹　

（中南财经政法大学信息与安全工程学院，湖北武汉４３００７３）　

摘　要：０—１背包问题是算法中的一个经典例子。　

对解题思路和时间复杂度进行了详细分析。　关键词：０—１背包；回溯法；分支限界；动态规划　

中图分类号：ＴＰ３１２　文献标识码：Ａ　

１　０—１背包问题介绍　用回溯、分支限界和动态规划这３种方法求解０—１背包问题，并　

给定ｎ个物品和一个背包，每个物品的重量为叫　，价　

值为　，背包的总容量为Ｃ。采用一种方法将物品放人背　

包，使得背包中的物品总价值最大。每个物品只有两种选　

择，放进背包或者不放进背包，即，２７　一１或者ｚ　一０，也即　

在满足∑　≤Ｃ，ｘ．∈［ｏ，１］的情况下，使得　值　

最大。　

例如，对于ｎ一４，Ｗ一［２，３，４，５］，Ｖ一［３，４，５，６］，　

Ｃ－＿５，最优解为Ｘ一［１，１，０，Ｏ］，最优值为７。　文章编号：ｌ６７２—７８００（２Ｏ１３）００８—００５９－０３　

２回溯法求解　

２．１　回溯法解题思路　

回溯法要求先构造一个虚拟的状态空间树，树的根部　

表示查找的初始状态，以深度优先（ＤＦＳ）的方式搜索整个　

空间树。从根结点开始，以它为活结点向下扩展，使下一　

个结点成为活结点，一直这样下去直至当前活结点无法向　

下扩展，此时这个活结点成为死结点，返回到离它最近的　

一个父结点，使这个父结点成为活结点，然后再向下扩展。　

当要求解出所有子集时，回溯法最终要回溯到根结点，并　

以及数据融合路径做进一步的研究。　

参考文献　

［１］　

［２］　

［３］　

［４］　

［５］　ＨＥＩＮＺＥＩ　ＭＡＮ　Ｗ　Ｒ，ＣＨＡＮＤＲＡＫＡＳＡＮ　Ａ．ＢＡＩ　ＡＫＲＩＳＨＮＡＮ　Ｈ．Ｅｎｅｒｇｙ—ｅｆｆｉｃｉｅｎｔ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ　Ｐｒｏｔｏｃｏｌ　ｆｏｒ　Ｗｉｒｅｌｅｓｓ　Ｍｉｃｒｏ　ｓｅｎｓ０ｒＮｅｔｗｏｒｋ［ｃ］．Ｐｒｏｃ．ｏｆ　ｔｈｅ　３３ｒｄ　ＩｎｔＩ　Ｃｏｎｆ　ｏｎ　Ｓｙｓｔｅｍ　Ｓｃｉｅｎｃｅ，　

WORD格式

专业资料整理

分治法

1、二分搜索算法是利用（ 分治策略）实现的算法。

9. 实现循环赛日程表利用的算法是（分治策略 ）

27、Strassen矩阵乘法是利用（分治策略 ）实现的算法。

34．实现合并排序利用的算法是（分治策略 ）。

实现大整数的乘法是利用的算法（ 分治策略 ）。

17．实现棋盘覆盖算法利用的算法是（分治法 ）。

29、使用分治法求解不需要满足的条件是（子问题必须是一样的 ）。

不可以使用分治法求解的是（ 0/1背包问题 ）。

动态规划

下列不是动态规划算法基本步骤的是（ 构造最优解 ）

下列是动态规划算法基本要素的是（子问题重叠性质 ）。

下列算法中通常以自底向上的方式求解最优解的是（动态规划法

备忘录方法是那种算法的变形。（ 动态规划法 ）

最长公共子序列算法利用的算法是（ 动态规划法 ）。

矩阵连乘问题的算法可由（动态规划算法 B）设计实现。

实现最大子段和利用的算法是（ 动态规划法 ）。

）

贪心算法

能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，

不能解决的问题：N皇后问题，0/1背包问题

是贪心算法的基本要素的是（贪心选择性质和最优子结构性质） 。

回溯法

回溯法解旅行售货员问题时的解空间树是（ 排列树）。

剪枝函数是回溯法中为避免无效搜索采取的策略

回溯法的效率不依赖于下列哪些因素（ 确定解空间的时间） WORD格式

专业资料整理

分支限界法

最大效益优先是（

分支界限法 ）的一搜索方式。

分支限界法解最大团问题时，活结点表的组织形式是（ 最大堆 ）。

分支限界法解旅行售货员问题时，活结点表的组织形式是（ 最小堆 ）

优先队列式分支限界法选取扩展结点的原则是（ 结点的优先级 ）

在对问题的解空间树进行搜索的方法中 ,一个活结点最多有一次机会成为活结点