实战训练:背包问题 构造解空间树 从n个物品中选取若干物品装载容量为M b1背包问题的一个解可以表示为一个n维向量 的背包;已知:第个物品的重量是w价 (X0Xy…xn-1)x=0或着1(i=01…n-1) 全部可能解有2n个 值是pi=0.n-1),且每个物品是无 可以采用下图所示的状态空间树 分割的。求:最优装载方案,即总重 量小于M,总价值最大 ■0-1背包问题,物品不允许切割 ⑤⑤6③d①④①66DQ 0-1背包问题状态树示例 搜索过程分析 ≌{12,1 {86,4,3},B=13 约束条件 搜空网:子集判,2个树叶 xP取最大值, 首先判断所有物品的重量和是否小于M 则按物品的价值置量比从大测小排列 在状态空间的任意一个部分解(xox1y…xk-1)处,应 当前部分解的总量 ·当前问慝状态下,繼深入搜可能找到比目前已知解的总 10手可行解:x0x1x1=,重:1: 斗引 子:可切割背包问题 Constraint和 bound函数 已知有n种物品和一个可容纳c重量的背 constraint()函数—实现简单 包,每种物品的重量为W假定物品的 bound函数 一部分放入背包会得到vx的效益。其中 好的 bound函数可以大大降低算法的复杂性 0≤x≤1v>0.采用怎样的装包方法才 会使装入背包物品的总效益最大呢? 在算法中设量一个变量bp,用来记录已搜宗到的解 状态空间结点〔叶结点)的最大值,初始值为0 ■非0-1,可以切割 每到达一个活动结点部分解,就调用 bound() 标函数 n约束条件 k≤C 0≤X≤L,H>0,W>0C>0回溯算法 19 实战训练：背包问题 „ 从n个物品中选取若干物品装载容量为M 的背包；已知：第i个物品的重量是wi ,价 值是 pi ,(i=0...n-1) ，且每个物品是无 法分割的。求：最优装载方案，即总重 量小于M，总价值最大。 „ 0-1背包问题，物品不允许切割 回溯算法 20 构造解空间树 „ 0-1背包问题的一个解可以表示为一个n维向量 (x0,x1,...,xn-1), xi =0或着1,(i=0,1,...,n-1) „ 全部可能解有2n个 „ 可以采用下图所示的状态空间树 1 X0=0 2 3 4 5 6 8 1 1 X1=0 13 7 9 0 0 12 15 0 1 10 11 16 1 14 20 0 0 1 1 17 18 19 21 0 1 22 24 1 1 0 23 27 0 0 26 28 0 1 25 29 30 1 0 31 1 1 X2=0 X3=0 1 1 回溯算法 21 0-1背包问题状态树示例 „ V={12,11,9,8}, W={8,6,4,3}, B=13 „ 结点：向量<x0 ,x1 ,…,x k-1>（子集的部分特征向量） „ 搜索空间：子集树, 个树叶 <0,1,1,1> 对应于可行解： x0=0, x1=1, x2=1, x3=1. 重量：13，价值：28 <1,0,1,0> 对应于可行解： x0=1, x1=0, x2=1, x3=0. 重量：12，价值：21 2 n 2 n 回溯算法 22 搜索过程分析 „ 约束条件 „ „ 取最大值， „ 首先判断所有物品的重量和是否小于M； „ 如果是，则解为(1,1,...1)，算法终止 „ 否则按物品的价值重量比从大到小排列 „ 在状态空间的任意一个部分解(x0,x1,...xk-1)处，应 该有以下两个判定指标： „ 当前部分解的总重量 „ 当前问题状态下，继续深入搜索可能找到比目前已知解的总 价值更大的解 1 0 n i i i x p − ∑ = 1 0 n i i i x w M − = ∑ ≤ 回溯算法 23 引子：可切割背包问题 „ 已知有n种物品和一个可容纳c重量的背 包，每种物品i的重量为wi 。假定物品i的 一部分放入背包会得到vi xi 的效益。其中 0≤xi ≤1,vi >0 . 采用怎样的装包方法才 会使装入背包物品的总效益最大呢？ „ 非0-1，可以切割 „ 目标函数 „ 约束条件 1 max n i i i V X = ∑ 1 0 1, 0, 0, 0 n i i i ii i WX C XVWC = ⎧ ⎪ ≤ ⎨ ⎪ ⎩ ≤≤ > > > ∑ 回溯算法 24 Constraint和bound函数 „ constraint( )函数——实现简单 „ bound()函数 „ 好的bound()函数可以大大降低算法的复杂性 „ 在算法中设置一个变量bp，用来记录已搜索到的解 状态空间结点（叶结点）的最大值，初始值为0 „ 每到达一个活动结点i(部分解), 就调用bound(i)