算法设计与分析 第四章.ppt

第四章 解答NP难解问题的 近似算法 4.1 近似算法及其性能评估 4.2 近似算法设计 4.3 多项式时间近似方案 4.1 近似算法及其性能评估 例: [存储最多程序问题] n个程序其存储所需容量分别为L1,L2,Ln以及两个磁盘其容量都为L 询问若不允许一个程序同时存放于两个磁盘内则这两个磁盘最多能存储多少个程序 易证这个问题是NP难解的该问题的近似算法A的一个简单描述如下: Step1: 对