分支限界法01背包问题_01背包问题

给定

$equation?tex=n$
个物品，每个物品都有其重量

$equation?tex=w_i$
和价值

$equation?tex=v_i$
以及一个容量为

$equation?tex=W$
的背包，01背包问题是在满足不超过背包容量的前提下在给定的

$equation?tex=n$
个物品中挑选若干个物品，使得所挑选的物品的价值总和最大。

经典的01背包求解方式是通过动态规划求解，算法的时间复杂度为

$equation?tex=O%28nW%29$
，但是这个算法实际上并不是一个多项式时间算法。我们一般衡量算法的时间复杂度是判断它是否是关于输入规模大小的多项式函数。

$equation?tex=W$
只是一个输入数据，它可以表示成输入规模

$equation?tex=n$
的指数形式，因此这个算法实际上是一个伪多项式算法。

实际上01背包问题是NP-hard的，我们无法在多项式时间求到它的最优解。但是我们可以在多项式时间内求到它的一个可行解。比如，我们可以用贪心算法来求解。对于每一个物品，按照它的性价比（价值/重量）排序，优先选择性价比高的物品。若

$equation?tex=%5Csum+w_i+%5Cle+W$
，则全选。不妨设

$equation?tex=v_1%2Fw_1%5Cge+v_2%2Fw_2%5Cge+%5Cldots+%5Cge+v_n%2Fw_n$
，假设

$equation?tex=k$
是满足

$equation?tex=%5Csum_%7Bi%3D1%7D%5E%7Bk%7Dw_i%5Cle+W%3C%5Csum_%7Bi%3D1%7D%5E%7Bk%2B1%7Dw_i$
的最大数值，那么将

$equation?tex=max+%5C%7Bv_%7Bk%2B1%7D%2C%5Csum_%7Bi%3D1%7D%5Ek+v_i%5C%7D$
作为算法的解。很显然的是，这样的贪心选择策略并不是正确的。假设我们有3个物品

$equation?tex=n_1%E3%80%81n_2%E3%80%81n_3$
,其重量分别为

$equation?tex=10%E3%80%8120%E3%80%8130$
，价值分别为

$equation?tex=60%E3%80%81100%E3%80%81120$
，其性价比分别为

$equation?tex=6%E3%80%815%E3%80%814$
。假设背包容量为

$equation?tex=50$
，则按照这个策略，应该选择

$equation?tex=n_1$
和

$equation?tex=n_2$
，所得价值为160。但是最优解是选择

$equation?tex=n_2$
和

$equation?tex=n_3$
，所得价值为220。虽然，这个贪心算法返回的一个局部最优解，但是我们可以证明在最坏的情况下，它返回的解至少是最优解的

$equation?tex=1%2F2$
。

证明之前，我们先简单了解一下近似算法。近似算法是针对一个优化问题而言的，该优化问题是一个最大化问题或者最小化问题。以最大化问题为例子，假设多项式算法

$equation?tex=%5Cmathcal%7BA%7D$
返回的值为

$equation?tex=sol$
，最优解为

$equation?tex=opt$
，我们用一个比值

$equation?tex=ratio%3Dmax%5C%7B%5Cfrac%7Bsol%7D%7Bopt%7D%2C%5Cfrac%7Bopt%7D%7Bsol%7D%5C%7D$
来衡量

$equation?tex=%5Cmathcal%7BA%7D$
返回的解跟最优解之间的偏离程度。这个比值，通常称为近似比。近似比越接近

$equation?tex=1$
，说明算法的效果越好。近似算法主要是为那些NP-hard的问题提供一个多项式时间的可行解的解决方案，可以理解成它是在时间代价和求解质量之间寻求一个平衡。近似算法与启发式算法最大的区别就是，近似算法是有严格的理论保证的，即它有近似比。近似比保证了算法在最坏情况下的性能。

按照上述贪心选择策略我们选择了前

$equation?tex=k$
个物品，即

$equation?tex=sol%3Dmax%5C%7B%5Csum_%7Bi%3D1%7D%5E%7Bk%7D+v_i%2Cv_%7Bk%2B1%7D%5C%7D$
。很明显，最优解

$equation?tex=opt$
满足

$equation?tex=opt%5Cle+%5Csum_%7Bi%3D1%7D%5E%7Bk%7D+v_i+%2B+%5Cfrac%7Bv_%7Bk%2B1%7D%7D%7Bw_%7Bk%2B1%7D%7D%28W-%5Csum_%7Bi%3D1%7D%5E%7Bk%7D+w_i%29%3C%5Csum_%7Bi%3D1%7D%5Ek+v_i+%2B%5Cfrac%7Bv_%7Bk%2B1%7D%7D%7Bw_%7Bk%2B1%7D%7Dw_%7Bk%2B1%7D%3D%5Csum_%7Bi%3D1%7D%5E%7Bk%2B1%7Dv_i%E3%80%82$

$equation?tex=sol%3Dmax%5C%7Bv_%7Bk%2B1%7D%2C%5Csum_%7Bi%3D1%7D%5Ek+v_i%5C%7D%5Cge+%5Cfrac%7B1%7D%7B2%7D%5Csum_%7Bi%3D1%7D%5E%7Bk%2B1%7D+v_i%3E%5Cfrac%7B1%7D%7B2%7Dopt$
，因此，该贪心算法的近似比为2。

若从另一个角度来看，假设我们将每个物品分成若干个小块，那么利用背包最有效的方式就是把前

$equation?tex=k$
个先装进背包，再装第

$equation?tex=k%2B1$
个物品的若干个小块，直到背包装满，因为这样性价比是最高的。这就意味着背包所能装的物品的总价值必然少于

$equation?tex=%5Csum_%7Bi%3D1%7D%5E%7Bk%2B1%7D+v_i$
，它是最优解

$equation?tex=opt$
的一个上界。

原文链接：https://blog.csdn.net/weixin_42524945/article/details/113330986

你可能也喜欢