增量计算背包

Question

有没有办法逐步计算背包问题？任何近似算法？我正在尝试解决以下场景中的问题。

让 D 成为我的数据集，它没有被排序，也不应该被排序。 D分为3个子集，即D1、D2和D3。如果需要，可以分别订购 D1、D2 和 D3。我想为集合 (D1,D2) 和 (D2,D3) 计算单独的背包解决方案，但我不想避免计算 D2 两次。所以，基本上，我想：

compute (D2) // 做一些操作
保存为中间结果
将其与 D1 一起使用并获得 (D1, D2) 的背包结果
将它与 D3 一起使用并获得 (D2,D3) 的背包结果

这样对D2的数据遍历只做一次。有没有办法像这样逐步解决背包问题？

Answer 1

维基百科给出了 0/1 背包的伪代码：https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem

 // Input:
 // Values (stored in array v)
 // Weights (stored in array w)
 // Number of distinct items (n)
 // Knapsack capacity (W)

 for j from 0 to W do:
     m[0, j] := 0

 for i from 1 to n do:
     for j from 0 to W do:
         if w[i-1] > j then:
             m[i, j] := m[i-1, j]
         else:
             m[i, j] := max(m[i-1, j], m[i-1, j-w[i-1]] + v[i-1])

这将构建一个二维数组，使得 m[n, W]（最后一行中的最后一个元素）是解决方案 - 你运行 D2 上的这个。

然后你编写另一个算法，将这个数组作为输入，

不执行 for j ... 部分来初始化数组
是否 for i from D2.count+1 to (D2.count + other.count) do: 从另一个停止的地方开始。（你必须在查找 w 和 v 数组时调整 i）

增量计算背包

Incrementally computing knapsack

algorithm

complexity-theory

knapsack-problem

approximation

subset-sum