[法学]第二章 背包问题.ppt

第二章 背包问题 第二章 背包问题 第二章 背包问题 * * 信息处理中的组合优化 第二章 背包问题 §1 背包问题的描述 §2 背包问题的分支定界法 §3 背包问题的近似算法 §4 0-1背包问题的一些相关问题 背包问题 ( Knapsack Problem ) 是一个有着广泛应 用的组合优化问题，它不仅在投资决策、装载、库存等 方面有应用，而且常以子问题形式出现在大规模优化问 题中，它的理论与算法具有一定的代表性. §1 背包问题的描述 背包问题的一般描述为：设有物品集 是一个准备放入容量为 的背包中的 n 项物品的集 合. 物品 的重量为 价值为 如何选择 U 中的一些物品装入背包，使这些物品的 总重量不超过 C ，且使总价值达到最大？ §1 背包问题的描述 背包问题的数学模型： 重量 价值 容量 因为决策变量 ,所以也称 0-1 背包问题. 一般背包问题: ( General Knapsack Problem ) 第二章 背包问题 为讨论方便，总可假定（相当于标准化）： 即按价值密度从大到小排列. 实际问题并非满足 §1 背包问题的描述 对 4 只需 O(nln n)次运算即可； 对 3 若 ，最优解为 ; 对 2 若 ，则最优解中 事先可去掉; 对 1 分三种情况讨论: (1) 若 且 令 此时，最优解中 所以，该物品事先可去掉; (2) 若 且 令 此时，最优解中 所以，该物品事先可去掉; 容量取 第二章 背包问题 (3) 若 且 令 只需在模型中，令 ，则系数即为大于零了. 综上，对不满足（1）、（2）、（3）的假定，可 作如下处理，使之满足： 对 令 对 令 则原问题化为： §1 背包问题的描述 如果在（KP）中，令 令 该问题的实际意义 是求不放在包中的物 品的价值和最小 . 模型的意义 Go back 第二章 背包问题 §2 背包问题的分支定界法 分支定界法 ( Branch and Bound Method ) 的基本 思想在运筹学课程中已介绍，它的重要在于它提出了一 类新的思路（隐枚举法），使得许多原来不好解决的问 题有了解决的可能性。（具有普适性） △ 确定问题（子问题）的最优值的界 极大（小）化问题 上（下）界 通常是通过求解松弛问题，用松弛问题的解作为界 Note : 松弛问题选择的原则 1、松弛问题要与原问题的最优值尽量接近； 2、松弛问题要尽量容易解 . 这两个原则不易统一，所以可选择不同的松弛问题 §2 背包问题的分支定界法 △ 划分方法的选择 原则是希望分出来的子问题容易被查清，可加快计算. △ 选哪个活问题先检查 1、先检查最大上界（极大化问题）的活问题 优点：检查子问题较其他规则为少； 缺点：计算机储存量较大 . 2、先检查必威体育精装版产生的最大上界的活问题 优点：计算机储存量较少 ； 缺点：需要更多的分支运算 . 选择的不同，提供了发挥的余地 第二章 背包问题 考虑 KP 的松弛问题 ： C(KP)如何求解？ 思路：将物品按价值密度从大到小的顺序放入包内, …… 记 —— 关键项 第一个放不下的 物品的序号 Theorem 2.1 §2 背包问题的分支定界法 C(KP) 最优解为 其中 最优解值为 proof 显然， ， 由于 的整数性， 得到 z ( KP ) 的一个上界： 表示不超过 的最大整数. Go on Go back 第二章 背包问题 Theorem 2.1 的证明 显然 C(KP) 的最优解必满足 设 是其最优解， 要证 若存在 使 则至少存在 使 . 取充分小的 (满足: ) 将 增加 减少 , 此时,仍是一个可行解, 且目标函数值增加