算法设计与分析课件 44 01背包问题3

算法设计与分析本节要点CONTENTS01背包问题分支限界法—01背包有n个物品和1个购物车，每个物品i对应价值为vi，重量wi，购物车的容量为W。每个物品只有一件，要么装入，要么不装入，不可拆分。如何选取物品装入购物车，使购物车所装入的物品的总价值最大？分支限界法—01背包（1）定义问题的解空间购物车问题属于典型的0-1背包问题，每个物品只有两种状态，要么装入背包，要么不装入。用xi表示第i种物品是否被装入背包，xi的取值为0或1。解的形式是一个n元组，且每个分量的取值为0或1。解的形式：{x1，x2，…，xi，…，xn}显约束：xi

=0或1分支限界法—01背包（2）确定解空间的组织结构解空间包括2n个可能解，即n个元素组成的集合所有子集个数。解空间树为子集树，解空间树的深度为问题的规模n。分支限界法—01背包（3）搜索解空间需要设置约束条件，判断背包的剩余容量是否大于等于物品的重量，如果剩余容量小于等于物品的重量，则不再搜索该分支。约束条件：rw≥w[i]。其中，rw表示背包的剩余容量，w[i]表示第i种物品的重量。分支限界法—01背包限界条件：up=cp+brp>bestp。其中，cp表示当前已装入背包的物品的价值，brp表示将剩余物品装满背包剩余容量获得的最大价值。分支限界法—01背包优先队列：将优先级定义为当前节点的价值上界up=cp+brp，最大值优先。搜索过程：从根开始进行广度优先搜索。首先扩展根，一次性生成其所有孩子，扩展左分支（约定左分支上的值为1），表示装入物品。若左分支满足约束条件，则将其加入优先队列；反之，舍弃。扩展右分支（约定右分支上的值为0），表示不装入物品。若右分支满足限界条件，则将其加入优先队列；反之，舍弃。然后从优先队列中取出一个节点扩展……直到队列为空时为止。分支限界法—01背包有4个物品，每个物品的重量w为（2，5，4，2），价值v为（6，3，5，4），背包容量W为10。求在不超过背包容量的前提下，将哪些物品放入背包，才能获得最大价值。分支限界法—01背包（1）对所有物品按价值重量比从大到小排序。把排序后的数据存储在数组w[]和v[]中。（2）创建根A并将其加入优先队列。当前已装入背包的物品重量cp=0，当前价值上界up=16.2，当前背包剩余容量rw=10，当前处理的物品序号为1，当前最优值bestp=0。分支限界法—01背包（3）扩展节点A。队头元素A出队，该节点满足限界条件up>bestp，可以扩展。背包剩余容量大于1号物品的重量，rw=10>w[1]=2，满足约束条件，可以装入背包，更新cp=0+6=6，rw=10-2=8。计算剩余物品装满背包剩余容量的最大价值brp。此时剩余容量为8，可以装入2、3号物品，装入后还有剩余容量2，只能装入4号物品的一部分，装入的价值为剩余容量×单位重量价值，即2×3/5=1.2，brp=4+5+1.2=10.2，up=cp+brp=16.2。分支限界法—01背包再扩展右分支，cp=0，rw=10，背包还剩余容量，可以装入2、3号物品，装入后还有剩余容量4，只能装入4号物品的一部分，装入的价值为剩余容量×单位重量价值，即4×3/5=2.4，brp=4+5+2.4=11.4，up=cp+brp=11.4，满足限界条件up>bestp，生成右孩子C并将其加入优先队列。分支限界法—01背包分支限界法—01背包

时间复杂度：

子集树的总节点数为20+21+…+2n=2n+1−1，先减去根再除以2，得到左、右孩子数都为(2n+1−1−1)/2=2n−1。约束函数和限界函数的时间复杂度均为O(1)。在最坏情况下，有O(2n)个左孩子需要调用约束函数，有O