第二章 背包问题.ppt

信息处理中的组合优化信息处理中的组合优化 第二章第二章 背包问题背包问题第二章第二章 背包问题背包问题§1 背包问题的描述背包问题的描述§2 背包问题的分支定界法背包问题的分支定界法§3 背包问题的近似算法背包问题的近似算法§4 0-1背包问题的一些相关问题背包问题的一些相关问题第二章 背包问题 背包问题背包问题 ( Knapsack Problem ) 是一个有着广泛应是一个有着广泛应用的组合优化问题，它不仅在投资决策、装载、库存等用的组合优化问题，它不仅在投资决策、装载、库存等方面有应用，而且常以子问题形式出现在大规模优化问方面有应用，而且常以子问题形式出现在大规模优化问题中，它的理论与算法具有一定的代表性题中，它的理论与算法具有一定的代表性.§1 背包问题的描述背包问题的描述 背包问题的一般描述为：设有物品集背包问题的一般描述为：设有物品集是一个准备放入容量为是一个准备放入容量为 的背包中的的背包中的 n 项物品的集项物品的集合合. 物品物品 的重量为的重量为 价值为价值为 如何选择如何选择 U 中的一些物品装入背包，使这些物品的中的一些物品装入背包，使这些物品的总重量不超过总重量不超过 C ，且使总价值达到最大？，且使总价值达到最大？§1 背包问题的描述背包问题的数学模型：背包问题的数学模型：重量重量价值价值容量容量 因为决策变量因为决策变量 , ,所以也称所以也称 0-1 0-1 背包问题背包问题. .一般背包问题一般背包问题: : ( General Knapsack Problem )第二章 背包问题为讨论方便，总可假定（相当于标准化）：为讨论方便，总可假定（相当于标准化）：即按价值密度从大到小排列即按价值密度从大到小排列. 实际问题实际问题并非满足并非满足§1 背包问题的描述对对 4 只需只需 O(nln n)次运算即可；次运算即可；对对 3 若若 ，，，，最优解为最优解为 ;对对 2 若若 ，则最优解中，则最优解中 事先可去掉事先可去掉;对对 1 分三种情况讨论分三种情况讨论:(1) (1) 若若若若 且且且且令令此时，最优解中此时，最优解中 所以，该物品事先可去掉所以，该物品事先可去掉;(2) (2) 若若若若 且且且且令令此时，最优解中此时，最优解中 所以，该物品事先可去掉所以，该物品事先可去掉; 容量取容量取第二章 背包问题(3) (3) 若若若若 且且且且令令 只需在模型中，令只需在模型中，令 ，则系数即为大于零了，则系数即为大于零了. 综上，对不满足（综上，对不满足（1）、（）、（2）、（）、（3）的假定，可）的假定，可作如下处理，使之满足：作如下处理，使之满足：对对对对 令令令令对对对对 令令令令则原问题化为：则原问题化为：§1 背包问题的描述如果在（如果在（KP）中，令）中，令令令 该问题的实际意义该问题的实际意义是求不放在包中的物是求不放在包中的物品的价值和最小品的价值和最小 . . . . 模型的意义模型的意义Go back第二章 背包问题§2 背包问题的分支定界法背包问题的分支定界法 分支定界法分支定界法 ( Branch and Bound Method ) 的基的基本本思想在运筹学课程中已介绍，它的重要在于它提出了一思想在运筹学课程中已介绍，它的重要在于它提出了一类新的思路（隐枚举法），使得许多原来不好解决的问类新的思路（隐枚举法），使得许多原来不好解决的问题有了解决的可能性。

具有普适性）题有了解决的可能性具有普适性）△△△△ 确定问题（子问题）的最优值的确定问题（子问题）的最优值的界界极大（小）化问题极大（小）化问题上（下）界上（下）界 通常是通过求解松弛问题，用松弛问题的解作为界通常是通过求解松弛问题，用松弛问题的解作为界Note : : 松弛问题选择的松弛问题选择的原则原则1 1、松弛问题要与原问题的最优值尽量接近；、松弛问题要与原问题的最优值尽量接近；2 2、、、、松弛问题要尽量容易解松弛问题要尽量容易解 . .这两个原则不易统一，所以可选择不同的松弛问题这两个原则不易统一，所以可选择不同的松弛问题§2 背包问题的分支定界法△△△△ 划分方法的选择划分方法的选择原则是希望分出来的子问题容易被查清，可加快计算原则是希望分出来的子问题容易被查清，可加快计算.△△△△ 选哪个活问题先检查选哪个活问题先检查1 1、、、、先检查最大上界（极大化问题）的活问题先检查最大上界（极大化问题）的活问题优点：优点：检查子问题较其他规则为少；检查子问题较其他规则为少；缺点：缺点：计算机储存量较大计算机储存量较大 . .2 2、、、、先检查最新产生的最大上界的活问题先检查最新产生的最大上界的活问题优点：优点：计算机储存量较少计算机储存量较少 ；；缺点：缺点：需要更多的分支运算需要更多的分支运算 . .选择的不同，提供了发挥的余地选择的不同，提供了发挥的余地第二章 背包问题考虑考虑 KP 的松弛问题的松弛问题 ：：：：C(KP)如何求解？如何求解？思路：将物品按价值密度从大到小的顺序放入包内思路：将物品按价值密度从大到小的顺序放入包内, ……记记 —— 关键项关键项第一个放不下的第一个放不下的物品的序号物品的序号?Theorem 2.1§2 背包问题的分支定界法C(KP) 最优解为最优解为其中其中最优解值为最优解值为proof 显然，显然， ，，由于由于 的整数性，的整数性，得到得到 z ( KP ) 的一个上界：的一个上界：表示不超过表示不超过 的最大整数的最大整数. .Go on Go back第二章 背包问题Theorem 2.1 的证明的证明显然显然 C(KP) 的最优解必满足的最优解必满足设设 是其最优解，是其最优解，要证要证若存在若存在 使使则至少存在则至少存在 使使 . 取充分小的取充分小的(满足满足: )将将 增加增加 减少减少 , , 此时此时, ,仍是一个可行解仍是一个可行解, ,且目标函数值增加且目标函数值增加 ,矛盾矛盾 .同理可证同理可证又由极大性知：又由极大性知：因此，因此， 是最优解是最优解. .Proof :§2 背包问题的分支定界法Theorem 2.2设设其中其中 与与 定义同前定义同前. .则则的一个上界为的一个上界为 ；；2、、对背包问题任一实例，对背包问题任一实例， .作为上界作为上界U2比比U1更更好好第二章 背包问题Proof :1、因为、因为 KP 中中 xs 不能取分数，不能取分数， 所以，所以，KP 的最优解一定是的最优解一定是 情形之一情形之一 .当当 ,由由 Th 2.1 可知，可知， 是此情形的上界是此情形的上界 ；； 当当 ,这时，若这时，若重量超出重量超出 ,而此时价值密度值最小的是而此时价值密度值最小的是 .是此情形的上界是此情形的上界 .从而从而 是是 的上界的上界 .§2 背包问题的分支定界法2、、要证要证 ，只需，只需证证是显然的是显然的；；C(KP) 的最优解值的最优解值C(KP) 当当 的最优解值的最优解值从而从而一般给出的上界越小，计算量越大，但越容易被剪枝一般给出的上界越小，计算量越大，但越容易被剪枝 .第二章 背包问题 书上给出了两类分支定界法书上给出了两类分支定界法 (广探法、深探法广探法、深探法) ，，实质是按什么条件来选结点进行分支，分支是对具有实质是按什么条件来选结点进行分支，分支是对具有最大价值密度的物品进行最大价值密度的物品进行 . 如下介绍的方法是参照确如下介绍的方法是参照确定定 U2 的思想，对关键项进行分支的思想，对关键项进行分支 .Example 1用分支定界法求如下用分支定界法求如下 KP :Solution :可验证可验证***Go back§3 背包问题的近似算法§3 背包问题的近似算法背包问题的近似算法 通过前面介绍的通过前面介绍的 C (KP) ，，自然想到如下贪婪算法自然想到如下贪婪算法(Greedy Algorithm):其目标函数值为其目标函数值为 .有改进的吗有改进的吗？？GA0step 1step 2若若 ,则则 ，，否则否则 ；；step 3若若 则结束则结束;否则否则转转GA0是近似是近似算法吗？算法吗？第二章 背包问题构造例子构造例子 I :按上述算法，得按上述算法，得：：为充分小的正数为充分小的正数 .而显然最优解为而显然最优解为：： 说明说明 GA0 的绝对性能比不会大于任意给定的正数的绝对性能比不会大于任意给定的正数,所以，它不能作为近似解所以，它不能作为近似解 . 但稍加改进，就可得到一但稍加改进，就可得到一个绝对性能比为常数的较好的近似算法个绝对性能比为常数的较好的近似算法 .§3 背包问题的近似算法GA1step 1step 2求解求解 C(KP)，得关键项记为，得关键项记为 s ;取取 作为近似解值作为近似解值 .即若即若 ，则，则否则否则Example 2Solution :显然，物品显然，物品3 为关键项（即为关键项（即 s = 3））易验证易验证而而近似解为近似解为有改进的吗有改进的吗？？用用 GA1 求如下求如下 KP :第二章 背包问题GA2step 1求解求解 C(KP)，得关键项记为，得关键项记为 s ;step 2令令若若则则否则否则Example 3用用 GA2 求如下求如下 KP :Solution :而而 近似解为近似解为Theorem 2.3proof§3 背包问题的近似算法Theorem 2.4证明与证明与 Th 2.3 的类似的类似 .对对Ex . 3考虑对考虑对 GA2 进行修改，进一步可取进行修改，进一步可取则则 这在实际计算中是会有好处的这在实际计算中是会有好处的 . 但绝对性能比不但绝对性能比不会改进会改进 .Go onTheorem 2.3 的证明的证明Proof :先证先证再说明不可改进再说明不可改进由由 s 的定义知：的定义知： 对于任意实例对于任意实例 I又又因此因此，，从而从而取实例取实例 I：：为充分小的正数为充分小的正数 .则则从而从而第二章 背包问题§3 背包问题的近似算法 已知已知 GA0 对解对解 0-1 背包问题效果很差，但在一般背背包问题效果很差，但在一般背包问题中却是可以的包问题中却是可以的 .设设显然，显然，是一个可行解是一个可行解 .通过求解通过求解 C(KP) 得得松弛问题的最优解值松弛问题的最优解值进一步可证进一步可证第二章 背包问题1975年年 Sahni 给出一个多项式时间近似算法给出一个多项式时间近似算法 .算法算法Sk :step 1对任意满足对任意满足且且 的子集的子集 M ，， 先将先将 M 中的物品放入包内中的物品放入包内,然后用算法然后用算法 GA1 或或 GA2 求解一个如下定义的求解一个如下定义的 KP ：：物品集为物品集为 N\M ，，包容量为包容量为 ，，将得到的解与将得到的解与M 的并作为原问题的近似解的并作为原问题的近似解 .step 2取上述所有不同解中最好一个作为输出取上述所有不同解中最好一个作为输出 .Theorem 2.5计算复杂性计算复杂性证略证略 参见教材参见教材 p99§3 背包问题的近似算法Theorem 2.6 如果如果 ，则背包问题不存在满足下，则背包问题不存在满足下述性质的多项式时间算法述性质的多项式时间算法 A : 存在固定的正整数存在固定的正整数 K 使得对任意的实例使得对任意的实例 I 有有Proof : 用反证法，假定存在，则可证明算法用反证法，假定存在，则可证明算法 A 可在多项式内可在多项式内精确地解精确地解 KP，但，但 KP 是是NP-C 的，这与的，这与 矛盾矛盾 . 给定给定 KP 任一实例任一实例 I ，将物品，将物品 j 的价值换成的价值换成 (K+1)pj, 而重量而重量wj 不变，包的容量不变，由此得到一个新的实例不变，包的容量不变，由此得到一个新的实例 I’ . 显然由显然由 I 构造构造 I’ 是在多项式时间内完成的是在多项式时间内完成的 . 用用 A 解解 I’ 得到的解，也是得到的解，也是 I的一个可行解的一个可行解 .算法算法A’: I I’, 用算法用算法 A 解解I’,得到得到 I 的可行解的可行解 . 算法算法 A’是多项式是多项式时间算法时间算法 由于由于 I 与与 I’ 有相同的可行解集，有相同的可行解集，I’ 的任一可行解值是的任一可行解值是 I 的的同一可行解值的同一可行解值的 （（K+1）倍，所以）倍，所以 由于由于 KP 任一可行解值为正整数，因此任一可行解值为正整数，因此 z A’ (I) = zopt (I)，这说明，这说明 A’ 总能得到实例总能得到实例 I 的最的最优优解，正是所需要的矛盾解，正是所需要的矛盾.Go back§4 0-1背包问题的一些相关问题背包问题的一些相关问题一、有界背包问题一、有界背包问题0-1 背包问题背包问题：：一般背包问题一般背包问题：：（无界背包问题）（无界背包问题）有界背包问题有界背包问题：：为给定的正整数为给定的正整数 .( Bounded Knapsack Problem )显然，显然，GKP 可化为可化为 BKP，只需令，只需令BKP 可化为等价的可化为等价的 0-1 KP思想思想：：任一整数可用任一整数可用 0 , 1 变量来表示，如变量来表示，如 非负整数非负整数如如 13第二章 背包问题Theorem 2.7记记则则（（1）） 是是 BKP 的一个上界的一个上界 ；；（（2））取取 得到一个可行解，将此解的值与得到一个可行解，将此解的值与 bs ps 的值比较的值比较,取大者为输出取大者为输出 .该算法的绝对性能比该算法的绝对性能比 , 计算复杂性为计算复杂性为 与前面讨论一样，总可假定与前面讨论一样，总可假定 都是正整数都是正整数;§4 0-1背包问题的一些相关问题二、子集和问题二、子集和问题 在组合优化问题中，很多问题是相通的，参数稍作在组合优化问题中，很多问题是相通的，参数稍作修正，可能就是另一个问题修正，可能就是另一个问题 .在在 0-1 背包问题中，令背包问题中，令 ( (这时这时 ) )即即称为子集和问题称为子集和问题Subset Sum Problem SSP 是是 0-1KP 的特殊情形，所以原方法皆可用的特殊情形，所以原方法皆可用. 但但因其特殊，它应有更简单的方法因其特殊，它应有更简单的方法 .第二章 背包问题1、、贪婪算法贪婪算法(GA)：： 按任意顺序将物品逐个放入包内，直到放不下为按任意顺序将物品逐个放入包内，直到放不下为止，然后将其结果与最大重量的物品比较，取优者为止，然后将其结果与最大重量的物品比较，取优者为输出输出 .可证可证计算复杂性为计算复杂性为 O(n) .2、、近似算法近似算法 MTGS :§4 0-1背包问题的一些相关问题将上述的贪婪算法分别用于物品集将上述的贪婪算法分别用于物品集取最好者为输出取最好者为输出 .这里假定这里假定 可证可证计算复杂性为计算复杂性为 O(nlogn+n2)=O(n2) .第二章第二章 背包问题背包问题 完完对如下背包问题对如下背包问题I：物品数：物品数n = 8 ，背包容量，背包容量 C = 60价值价值 （（p1，，p2，，…，，p8））= （（85，，26，，39，，37，，112，， 5，，10，，15））重量重量 （（w1，，w2，，…，，w8））= （（41，，13，，20，，19，，59，， 3，，7，，12））1、选择、选择GA1或或GA2求求 I 的近似解；的近似解；2、用分支定界法求解、用分支定界法求解 I 。