0-1背包：在空间优化实现中找到解决方案集

Question

这里的一个明显问题是，对于我所考虑的维度，这种方法消耗的内存将超过可行的（需要O(n*w)空间，N是元素数，W是最大容量）。进一步研究，我发现提到了（例如，这里也参见Kellerer，Pferschy和Pisinger的“背包问题”）一个内存有效的方法来解决0-1背包。

我们首先将项目集合分成大小大致相等的两个子集。我们将这两个子集视为它们自己的背包问题，给定初始的最大权重w，并以节省内存的方式为这两个子集确定最大利润计算的最后一行（详见上文）。

下一步是找出在哪里最优地拆分这两个子集。为此，我们确定两行的重量W1和W2的最大利润。据我所知，维护w1+w2=w是至关重要的，因此我遍历第一行，并在当前索引的另一端获取索引。此步骤的当前实现如下所示：

def split(weights, values, n, w, i):
    # s1 is the bigger subset size if n is not even
    s1 = n // 2 + (n&1)
    s2 = n // 2

    row1 = maximum_profit(weights, values, s1, w)
    row2 = maximum_profit(weights[s1:], values[s1:], s2, w)

    max_profits_for_capacity = [x + y for x, y in zip(row1, row2[::-1])]
    max_profits = max(max_profits_for_capacity)                           
    optimal_weight_index = max_profits_for_capacity.index(max_value)

    c1 = row1[optimal_weight_index]
    c2 = row2[w-optimal_weight_index-1]

split(weights[:s1], values[:s1], s1, c1, i)      
split(weights[s1:], values[s1:], s2, c2, i+s1)

这就是我失去描述的地方。最后，这段代码将递归到n==1，其值为w。在给定项索引I和最大（本地）容量w的情况下，如何确定是否包含元素？

我可以提供一个小的示例数据集来详细说明我的代码的工作方式以及哪里出错。非常感谢。

Answer 1

首先，我想您把C、W和它们作为容量的关系说错了，但是从利润列表中获得C1和C2。

对于问题，通过分裂函数的返回值，您可以定义您正在回答的问题类型。

当您采用直接到n==1点的拆分，并且希望将所选项的索引获取到背包中时，只需在这一步返回由[0]或[1]组成的值作为输出：

if n == 1:
  if weights[0] < w:
    return [1]
  return [0]

• [1]表示将项选入结果集
• [0]否则

然后在split函数递归的其他步骤中将它们连接成一个，如下所示：

def split(..):
  ..
  # since it is lists concatenation
  return split(weights[:s1], values[:s1], s1, c1, i) + split(weights[s1:], values[s1:], s2, c2, i+s1)

结果，您将得到大小n的列表（表示拆分的项数），其中有0和1。

null