背包问题 usaco

背包问题

译 by 铭

（在中国，背包问题一般是这样描述的：设n个重量为（W1,W2,...Wn）的物品和一个载重为S的背包，将物品的一部分xi放进背包中的利润是Pixi，问如何选择物品的种类和数量，使得背包装满而获得最大的利润？另有一简化版本说：设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1,W2,...Wn。问能否从这n件物品中选择若干件放入此背包，使得放入的重量之和正好为S。--译者加，不知道有没有班门弄斧之嫌）

前提

●贪心法（它是一种多步决策法，它总是作出在当前看来是最好的选择，它的考虑不是从整体出发，而只是某种意义上的局部最优，这样贪心法不能对所有问题达到整体最优解，但是对相当范围的许多问题都能够产生整体最优解。--译者） ●动态规划（它是将问题进行逐步的划分来缩小问题的规模，直到可以求出子问题的解为止。分划子问题后，对应的子问题中含有大量的重复，这样就将重复地求解；在第一次遇到重复时把它解决，并将解保存起来，以备后面引用。动态规划法常用来求一个问题在某种意义下的最优解。--译者） ●递归下降

示例问题：用录音带录音

农场主约翰最喜欢的爱好是制作一个Bessie喜欢的音乐合集磁带以便它在产奶时听。Bessie的产奶量取决于它产奶时所听的歌曲。

已知一组歌曲（每首歌都由一对整数－－此曲的长度（以秒计），听该首歌时的产奶量来表示）以及给挤奶的总时间。找到这样一组歌曲的集合，使得歌曲的总长度不超过给Bessie挤奶的总时间且使Bessie的产奶量达到最大。

抽象描述

已知一组物品--每个都有其尺寸和值（比如，重量），以及可用的总空间。找到这样一个集合，使得该集合的值的和最大，且其尺寸的和受某些限制所约束。集合中任何一个特定的项目的总数目/尺寸不能超过它的可利用率。

解题想法

视其为背包问题的一般方法是一个容量受限的背包使得放入其中的物品的值达到最大。

以上述问题为例，Bessie产奶时听的音乐带就是“背包”，而那些歌就是“放入背包中的物品”。

三个背包问题

背包问题有三种形式： ●小数背包问题

允许将小数表示的物品放入背包中的是小数背包问题。举例来说，如果物品是原油、飞机燃料、煤油而你的背包是一只水桶，取0.473升的原油，0,263升的飞机燃料和0,264升的煤油就是有意义的。这是形式最简单的要解决的背包问题。 ●整数背包问题

在整数背包问题中，只有完整的物品能放入背包里。此形式的一个例子就是：部分的曲子不允许放入包中。 ●多重背包问题

在多重背包问题中，需被填充的背包多于一个。如果允许有小数的物品放入，也就等于有一个大的背包，其容量相当于所有可用背包的和。因此，此术语只用来指多重整数背包的情况。

小数背包问题

小数背包问题是三者中最简单的，其贪婪解法如下： ●找到“值密度”（物品值/尺寸）最大的物品

●如果总容量仍就超过物品的可利用率，把所有满足条件的物品放入背包中，然后反复执行。

●如果总容量少于物品的可利用率，尽可能多的使用可用空间，然后终止。 ●由于这个算法必须先按照值密度把物品分类，然后以降序将它们放入背包，直至容量用完，该算法以N log N 级运行。通常简单些的方法不是将它们分类，而是不停地找每次不用的最大值密度，这种算法的时间复杂度是O(N 2) 。 注意：对于这类问题，因为你可以做一个微小的变换使得所有的物品尺寸大小为一，且原始尺寸大小和可利用率（当然用原始尺寸大小除值）的乘积就是总容量，同时有尺寸和可利用率是很少见的。

延伸：在这种情况下，物品的值和可利用率可以是实数。用这种算法处理有小数的尺寸大小也不是问题。

整数背包问题

这个问题有点难度，但是如果背包足够小，使用动态规划，它还是可解的。 ●依据背包大小的最大值设计动态的程序。 ●刷新用来表示大小为S的物品的数组，颠倒其次序，看将当前物品放入大小为K的背包中所产生的集合是否比当前最好的大小为K+S的背包更符合条件。 ●这个算法运行K*N次，其中K是背包的大小，N是物品的可利用率义之和。 ●如果背包太大了以至于无法分配此数组，递归下降是一种选择，即这个问题是NP完全的（给定I上的一个语言L，如果有一架非确定图灵机M和一个多项式P(n)，对任何I上的长度为n的串w，M都可以在P(n)步内确定是否接受w，则称L是非确定图灵机下多项式时间复杂性问题，简记为NP问题/语言。若L是属于NP的，且对NP中的每一个语言L'，都存在一个从L'至L的多项式时间转化，我们说L是NP完整的。--译者）。当然，递归下降在以小的物品填充的大背包

情况下可以运行相当长的一段时间。 延伸：

●小数的值不是问题；数组可以用实数数组来代替整数数组。小数的可利用率并不影响什么，在没有大量损失的条件下，缩短数字（如果你有3,5个物品，你可以仅用3）。

●小数的尺寸是个讨厌的东西，它使得问题递归下降。

●如果尺寸都相同，问题就能贪婪地解开，在下降的值排序中选择物品，直到背包满为止。

●如果值都是1.0，同样地使用贪心法，在上升的尺寸大小排序中选择物品，直到背包满为止。

多重背包问题

对于任何大小的多重背包，状态空间太大了以至于无法使用从整数背包算法中来的DP解法。于是递归下降是解决这个问题的方法。 延伸：

●用递归下降，通常扩展就简单了。小数的尺寸和值就不是问题了，同样地值的计算功能也不是问题。

●如果值都是同一个，那么如果能被放入所有背包中的物品的最大值是n，则存在使用n个最小物品的解法。它能大大减少查找时间。

示例问题

分数膨胀[1998 USACO National Championship]

你正试图设计一个有最高分数(<10,000)的比赛。已知比赛长度，一组问题，问题的长度以及每个问题的分值，计算满足长度约束的最高分数的比赛。

分析：这是一个整数背包问题，比赛是背包，尺寸是问题的长度，值是分数值。背包（比赛）尺寸的限制是其足够小使得解法在存储器中运行。

篱笆栏[1999 USACO Spring Open]

农场主约翰准备在他的领地建一圈篱笆。他已装好了柱子，所以他知道所要的围栏长度。当地的木材店有各种长度的木板（至多50个）。已知木材店木板的长度，约翰要的围栏长度，计算约翰建篱笆所用的围栏最大值。

分析：这是个多重背包问题，木材店的木板是背包，物品是约翰用的围栏。物品的尺寸就是长度，值是一。

由于值都是一，如果存在用任意K个围栏的解法，则有用K个最小围栏的解法。

装满你的油箱

你在Beaver郡中部一百英里有一个加油站的城市中，想将你的油箱装满好能到达Rita Blanca。幸运地是，这个小镇有两三个加油站，但它们的油都好像要用光了。已知每个加油站的油价，每个加油站的油量，计算为了花最少的钱，应该

从每个加油站买多少汽油。

分析：这是一个小数背包问题，背包是油箱，物品是汽油。