分组背包问题
有N件物品和一个容量为V的背包.第i件物品的 费用是c[i],价值是w[i].这些物品被划分为若 干组,每组中的物品互相冲突,最多选一件.求 解将哪些物品装入背包可使这些物品的费用总和 不超过背包容量,且价值总和最大.
有依赖的背包问题
这种背包问题的物品间存在某种"依赖"的关 系.也就是说,i依赖于j,表示若选物品i, 则必须选物品j.为了简化起见,我们先设 没有某个物品既依赖于别的物品,又被别的 物品所依赖;另外,没有某件物品同时依赖 多件物品.
这样我们就得到一个更好的上界.U1 是由Dantiz给出, U2 是由Martello和grange给出的.
广探法
用根结总表示原背包问题,求出它的上界; 在根节点通过取 x1 = 1, x1 = 0 , 进行分枝,得到两个子 问题,分别计算这两个子节点对应背包问题的上界. 选取具有最大上界的节点进行分枝.对选取的节点, 设物品j为尚未确定是否放入包内的物品,且它在这类 物品中具有最大价值密度,则通过取 x j = 1,x j = 0 ,进 行分枝产生两个子节点. 在分枝过程中,若某个子节点的上界小于当前原问题 的某一个可行解值,则该子节点删去不再进行分枝.
深探法
如果在某节点处的分枝 x j = 1 对应的子问题不可行, 则删去分枝,回到分枝 x j = 0 对应的子问题继续进行. 若某一个分支进行到最后一个物品,则可产生一个可 行解,将它与已有的其它的可行解进行比较,保留最 好的一个,然后回到最迟发生的某个 x j = 0 分枝继续 进行. 在上述过程中若某子节点上界小于当前已有的可行解 值,则该子节点删去.
s 1
定理
设 U =
0
∑
s 1 i =1
p s +1 1 pi + c ,U = w s +1
∑
s 1 i =1
p s 1 pi + p s ( wi c ) w s 1
背包问题的一个上界为U 2 = max(U 0 , U 1 ) ; 对于背包问题的任意一个实例都有 U 2 ≤ U1 .
作业
P102 1,3,5
�
Knapsack Problem 背包问题
背包问题
定义: 个不同物品和一个背包, 定义: 有N个不同物品和一个背包,其 中: 物品具有重量, w2 … wn ) 和价 ( w1 值 ( p1 , p 2 … p n ) 背包的最大重量承受限制为C 背包的最大重量承受限制为C 如何放置物品可得最高价值? 如何放置物品可得最高价值?
x j = 1, j = 1, 2 ...., s 1, x j = 0 , j = s + 1, ...., n , x s =
c , ws
ps ws
其中
c = C ∑ wi
i=1
s 1
,其最优解值为
z =
∑
s 1 i =1
pi + c
.
根据此定理,我们得到背包问题的第一个上界
ps U1 = ∑ pi + c i =1 ws
其它类型背包问题
完全背包问题(0/1) 多重背包问题 分组背包问题 有依赖的背包问题
完全背包问题
有N种物品和一个容量为C的背包,每种物品 都有无限件可用.第i种物品的体积是wi, 价值是pi.求解将哪些物品装入背包可使这 些物品的费用总和不超过背包容量,且价值 总和最大.
多重背包问题
有N种物品和一个容量为C的背包.第i种物 品最多有ni件可用,每件体积是wi,价值是 pi.求解将哪些物品装入背包可使这些物品 的费用总和不超过背包容量,且价值总和最 大.
分枝定界法求极大化问题的步骤
3. 在B的最优解中任选一个取值不符合整数条件的变 量 x j ,其值为 β j ,构造两个约束条件 xj ≤ β j , xj ≥ β j +1
将这两个约束条件分别加入B中,得到两个后继子规划 B 1和 B2 . i 4. 对每一个后继问题 Bi ,设解为 x ,若为整数,则停止 分枝,若此时对应目标值目标值 z i > z , 则其 zi z , i 作为新的下界;若 x 非整,且 zi ≤ z 则也停止分枝; i 若 x 非整,且 z i > z 则按照3中的方式进行分枝.
min z = 4 x1 9 x2 s.t.9 x1 + 7 x2 ≤ 56 7 x1 + 20 x2 ≤ 70 x1 , x2 ≥ 0
4.81 得最优解 x = 1.82
0
z 0 = 35.6
得一下解,记为
z
.
又 x = 显然是目标值的一个可行解,对应目标值为0是A的一个上界, 0 记 z = 0 ,因此有 35.6 ≤ z * ≤ 0 .
max
n
z = ∑ pjxj
j =1
n
s.t
∑w x
j =1 j
j
≤C
0 ≤ xj ≤1
记此问题为C(KP)
考虑一个基本算法:将物品按价值密度从大到小进行排 列一个个放入包内,设物品s是第一个放不下的物品, 称它为关键项,即
s = min{ j | ∑ wi > C}
i =1 n
定理
背包问题对应的松弛问题C(KP)的最优解为
深探法
用根结总表示原背包问题,求出它的上界; 对于根节点通过生成两个子节点 x1 = 1,x1 = 0,分别计算 得到问题的上界,从 x1 = 1 对应的子节点出发继续分 枝过程. 设当前对某个子节点进行分枝,设物品j是尚未确定是 否放入包内的物品,且它在这类物品中具有最大价值 密度,则通过取生成两个子节点 x j = 1, x j = 0 ,计算上 界.继续从对 x j = 1 应子节点出发进行搜索.
即 z = 3 4 ,且 B3 不用再进行分枝了.再求解 B4 得解 了.
1.42 ,目标值 z = 32.7 > z 3
,所以不能再进行分枝
2 x2 进行分枝. 同样在 B2 中取
最终得最优解 x* = 4 , z* = 34 . 2
背包问题的分枝定界法
先对背包问题进行松弛
分枝定界法求极大化问题的步骤
* 5.当所有子问题均不能再分枝时,z 即为最优目标值 z , * 对应的解即为最优解 x .

举例
min z = 4 x1 9 x2 s.t.9 x1 + 7 x2 ≤ 56 7 x1 + 20 x2 ≤ 70 x1 , x2 ≥ 0 x1 , x2为整数
先考虑松弛问题
5 x2 = , z1 = 34.1, 1.57
非A的可行解,顾 z 不变.
在 B1 中取 x1 进行分枝,分别在 B1 中添加约束条 2 件 x 2 ≤ 2, x 2 ≥ 3 ,得到新的子问题 B 3 , B 4 ,求解 B3
4 解 2
,得
,为整解,目标值为 34 < z ,做为新的上界, ,
0
在B的最优解中任选取一个取值非整的变量,比如我们 选 x1 ,对B分别增加约束条件 x 1 ≤ 4 , x 1 ≥ 5 得到两个子问题 B1 和 B2
B B1 : x1 ≤ 4
B B2 : x1 ≥ 5
B2
再分别求解 和
B1
和
,得到
4 x1 = , z1 = 34.9, 2.1
假定
1 .w
2 .w
n
j
> 0, p
j
j
> 0
≤ C
3.∑ w j ≥ C
j =1
4.
p p p1 p ≥ 2 ≥ 3…≥ n w1 w2 w3 wn
背包问题转化为极小化问题
令x
j
= 1 y j,Q =
∑
n
j =1
wj C
min
n
z = ∑ pj yj
j =1
n
s.t
∑w y
j =1 j
j
≥Q
0-1背包问题
此问题可以表示为: 此问题可以表示为:
注意:这种问题是 种不同的物品 每种物品只有两种状态: 种不同的物品, 注意:这种问题是n种不同的物品,每种物品只有两种状态: 出现或者不出现在背包里, 的取值为0或者 或者1, 出现或者不出现在背包里,所以 x j 的取值为 或者 ,所 以这种背包问题又称为0-1背包问题. 背包问题. 以这种背包问题又称为 背包问题
分枝定界法求极大化问题的步骤
0. 设有整数线性规划问题A,与之相对应的松弛问题为B. 1. 求解问题B,可能产生下列情况之一: B没有可行解,这是A也没有可行解,停止. B有整数最优解,则B的最优解即为A的最优解,停 止; B有最优解,但不符合问题A的整数约束,记他的目 _ 标函数值为 z ,作为问题A的上界.
xj = 0或 1
分枝定界法
主要思想是:设有极大化的整数线性规划问题A,用B表示 A去掉整约束而得到的松弛问题,从求解B开始,若其 最优解是整解,则已得A的最优解,否则B的最优目标 _ * 值必是A的最优目标值的 z 的上界,记为 z ;而A的任 意可行解的目标函数值必是最优解的一个下界 z ,分 枝定界法就是将可行域分成子区域,逐步增大下界,最 终求出最优解的方法.