6

对于有界背包问题，假设每个项目的值与其重量相同并且所有重量都是正整数，我想知道是否有针对单个项目重量与项目数量相比较小的情况进行优化 n和背包的容量是所有物品重量总和的一半？例如 100k 个项目，每个项目的权重限制为 [1, 10]。

该算法应该给出精确的解决方案。我知道 O(n*W) 时间和 O(W) 空间 DP 算法，但认为在这种情况下可能有更好的方法来解决它。提前致谢。

这是来自算法挑战，O(n*W) 时间解决方案在功能上是正确的，但速度不够快（比所需的速度慢一个数量级）。我似乎在这个问题上找不到任何东西。输入是物品重量列表，所需输出是可以装入背包的物品的最大总价值。

4

2 回答 2

6

您正在寻找的论文是 Pisinger 1999，“Linear Time Algorithms for Knapsack Problems with Bounded Weights”。不过，这有点痛苦，因为 pdf 似乎已经失去了某些变量的区别标记。

以任何顺序将项目添加到您的解决方案中，直到您到达项目b -中断项目- 这导致您超过W。1, 2, ... b-1项构成平衡填充，其他所有平衡填充都是通过一系列两个操作可以达到的：

  • 平衡插入是在重量<= W的平衡解决方案中添加b或更高位置的项目。
  • 平衡删除是从权重> W的平衡解决方案中删除b之前的项目。

很容易看出两件事：首先，所有平衡解决方案都在W的 10 个重量单位内，其次，最佳解决方案必须是平衡解决方案。

我们通过动态规划找到了从初始解到最优解的方法。

  • 对于从b开始的每个项目t ，
  • 并且对于每个权重w使得W - 9 < w < W + 10，
  • 我们将跟踪b之前的最新项目s
  • 这样就可以通过仅在s和t之间添加/删除项目来实现重量w的平衡填充

读几遍。请注意，在此过程中的某个时刻，我们保证会遇到最佳解决方案（尽管直到最后我们才会知道）。让wBreak为添加中断项之前的权重，我们的算法初始化为：

for (w = W-9, w <= W, w++) { s(b-1, w) = 0 }
for (w = W+1, w <= W+10, w++) { s(b-1, w) = 1 }

s(b, wBreak) = b - 1

这些都是默认值，除了s(b, wBreak)。然后我们开始吃肉：

for (t = b, t <= N, t++) 
{
    for (w = W-9, w <= W, w++) 
    {
        // Trying adding item t to the solutions with weight <= W 
        s(t, w + w_t) = max( s(t-1, w), s(t-1, w + w_t) )   
    }
    for (w = W+10, w > W, w--)
    {
        // Removing as many items as needed to get back to a balanced filling
        for (j = s(t, w) - 1, j >= s(t-1, w), j--) 
        {
            s(t, w - w_j) = max( s(t, w - w_j), j )
        }
    }
}

总之，这需要O(N)时间，我们可以将最优填充的权重识别为非平凡的 s(t,w)，其中w最接近W但不大于它。

请注意，这并没有利用所有项目的权重总和为 2W 的事实。我会尝试考虑使用它进行简化，但这可能是设置者添加的问题，因此当没有足够的项目来填充 W 时，您不必担心琐碎的边缘情况。

于 2013-09-22T22:01:06.693 回答
1

Pisinger 1999 年的论文 Bounded Knapsack 可以在 http://www.diku.dk/~pisinger/94-27.ps找到 ，实现的代码在 http://www.diku.dk/~pisinger/codes.html 为bouknap.c

于 2015-05-08T16:54:23.183 回答