izh*_*hak 9 algorithm knapsack-problem
关于背包问题的维基百科文章包含三种类型的列表:
1-0(一种类型)
有界(一种类型的几个项目)
无界限(无限数量的项目)
本文包含针对1.和3.类型问题的DP方法,但没有针对2的解决方案.
如何描述用于求解的动态编程算法？
提到的其他 DP 解决方案都是次优的，因为它们需要您直接模拟问题，从而导致O(number of items * maximum weight * total count of items)运行时复杂性。
有很多方法可以对此进行优化，我将在此处提及其中的一些：
一种解决方案是应用类似于 Sqrt 分解的技术，并在此处进行了描述：https : //codeforces.com/blog/entry/59606。该算法在O(number of items * maximum weight * sqrt(maximum weight)).
然而，Dorijan Lendvaj 描述了一个运行在O(number of items * maximum weight * log(maximum weight))这里的更快的算法：https : //codeforces.com/blog/entry/65202?#comment-492168
考虑上述方法的另一种方式如下：
对于每种类型的项目，让我们定义以下值：
w, 当前类型物品的重量/成本v, 当前类型项的值n, 当前可供使用的物品类型的副本数首先，让我们考虑小于或等于2^k的最大幂。我们插入以下项（每个插入项的格式为）：, , , ..., 。需要注意的是插入的项目分别表示，，...，分别为目前类型的物品的副本。2n(weight, value)(w, v)(2 * w, 2 * v)(2^2 * w, 2^2 * v)(2^(k-1) * w, 2^(k-1) * v)2^02^12^(k-1)
请注意，这与插入2^k - 1当前项目类型的副本相同。这是因为，我们可以模拟任何数量的项目（表示为的采取n'通过采取上述项目的组合），其对应于二进制表示n'（对于所有整数k'，如果该位代表2^k'被设定，取代表该项目2^k'当前类型项目的副本）。
最后，我们只插入与 的设置位对应的项目n - (2^k - 1)。（对于所有整数k'，如果2^k'设置了表示的位，则插入(2^k' * w, 2^k' * v)）。
现在，我们可以n通过组合上述插入的项目来模拟最多当前类型的项目。
我目前没有这个解决方案的确切证据，但在玩了一段时间后，它似乎是正确的。如果我能弄清楚，我可能会在稍后更新这篇文章。
首先，一个命题：我们需要证明的是，插入上述项目允许我们模拟取任意数量的当前类型的项目，直到n。
考虑到这一点，让我们定义一些变量：
n成为当前类型可用的项目数x是我们要利用目前类型的项目数k是最大的整数，使得2^k <= n如果x < 2^k，我们可以x使用算法的第 1 阶段中描述的方法轻松获取项目：
...我们可以通过取与 n' 的二进制表示相对应的上述项目的组合来模拟取任意数量的项目（表示为 n'）（对于所有整数 k'，如果表示 2^ k' 已设置，取代表当前项目类型的 2^k' 个副本的项目）。
否则，我们执行以下操作：
拿n - (2^k - 1)物品。这是通过获取在阶段 2 中插入的所有项目来完成的。现在只有阶段 1 中插入的项目可供使用。
拿x - (n - (2^k - 1))物品。由于这个值总是小于2^k，我们可以只使用第一种情况使用的方法。
最后，我们怎么知道x - (n - (2^k - 1)) < 2^k？
如果我们简化左侧，我们得到：
x - (n - (2^k - 1))
x - n + 2^k - 1
x - (n + 1) + 2^k
如果上述值为>= 2^k，则为x - (n + 1) >= 0真，即x > n。那是不可能的，因为这不是 的有效值x。
最后，这里甚至还提到了一种O(number of items * maximum weight)及时运行的方法。
该算法类似于ic3b3rg提出的蛮力方法，只是使用简单的 DP 优化和滑动窗口双端队列来降低运行时间。
我的代码在这个问题上进行了测试（经典有界背包问题）：https : //dmoj.ca/problem/knapsack
我的代码：https : //pastebin.com/acezMrMY