PACT 07/06 线规舍入 + 背包问题
线性规划舍入(LP Rounding)
对于很多的问题,我们都可以写出一个对应的整数规划(IP),然而写成整数规划本身没有啥用,因为整数规划也是
的。但是整数规划可以通过松弛转变为线性规划,后者是可以在多项式时间内求解的,这就给近似算法的设计提供了一个思路。
唯一的问题是,线性规划给出的解未必就是整数了(在例如网络流问题等特殊的问题下还是有可能的),因此我们需要在确保解的可行性的前提下对于线性规划的解进行舍入,这个技巧便成为LP rounding。
以带权顶点覆盖问题为例,其整数规划为
其松弛后的线性规划为
于是就需要舍入。如何舍入?设线性规划最优解时,整数规划的解
,则
注意到如果按照这么舍入,,又注意到线性规划的最优解一定不大于原整数规划的最优解,即
:
背包问题
定义
输入:件物品,每一件物品有重量
和价值
,以及背包容量
。
目标:在物品总重不超过背包容量的前提下使得打包的物品价值总和最大。
贪心算法
一个非常简单直接的想法是按照价重比()贪心,但是这个贪心非常容易被卡掉,比如说有两个物品,第一件物品的重量为
,价值为
,第二件物品的重量和价值都是
,那按照价重比贪心我会先选第一件,然后之后就不能选第二件了,这个方案就很糟糕,而且和最优解的差距可以任意大。
但是有一个简单的小优化:假设物品是我们第一个因为放不下不选的物品,我们最后在贪心的方案和物品
单件中择优输出,这个算法一下子就会好上很多——事实上这就是一个
倍近似算法了。
证明:分两种情况。
- 贪心方案的总重
。因为我们是按照价重比贪心的,因此最优解的总价重比不会大于我们贪心方案的价重比,而贪心方案的重量至多是
,因此此时我们贪心方案的总价值至少为最优方案的
。
- 贪心方案的总重
。装不下下一个,说明接下来的物品是重量
的大块头,令这个物品为
。这样的大块头在任何打包方案当中都至多塞一个。此时最优解总价值不大于当前贪心解价值与
之和(这个论断可以通过画图的方式进行证明,目前似乎还没有找到更有说服力的纯文字证明)。因为我们最后择优输出,因此我们最终方案的总价值至少是最优方案的
。
动态规划
背包问题的动态规划是老生常谈的问题了,时间复杂度是,看起来是多项式?其实不然,因为
有关的信息只需要
个比特存储,因此这个时间复杂度实际上是和输入长度成指数级的。
多项式时间近似方案(PTAS)
接下来我们提供背包问题的一个多项式时间近似方案(PTAS)。什么是PTAS?一个PTAS可以认为是一类基于参数的算法,且参数为
的算法构成问题的
倍近似(对于最大化问题则可以是
倍近似)。算法的运行时间可以和
成指数级(因为在每一个算法当中,
被视作常数),如果算法的运行时间和
成多项式级,则这个PTAS被称为完全多项式时间近似方案(FPTAS或FPAS)。
要设计这个算法,我们先从DP入手。考虑背包问题的如下DP:设是考虑前
个物品,总价值为
时的最小总重,则有如下转移:
因此我们的PTAS是:对于每件物品,对其价格等比例缩小舍入,新的价格为。随后进行DP,并输出DP的最优解。设最优解为
。
这样一来我们的总价格是多少呢?(定义表示集合的价格)。
若令,则有
因此这个算法确实是一个PTAS。这个算法的运行时间是多少呢?