1

我正在开发一个程序来解决 0/1 背包问题的变体。

此处描述了原始问题：https ://en.wikipedia.org/wiki/Knapsack_problem 。万一以后链接丢失了，我给大家总结一下 0/1 背包问题（如果你熟悉的话，跳过这一段）：假设我们有n物品，每个物品都有重量wi和价值vi。我们想把物品放在一个支持最大重量的袋子里，W这样袋子里的总价值就是最大可能的，而不会使袋子超重。项目不能有多个实例（即，我们每个实例只有一个）。问题的目的是maximize SUM(vi.xi)使SUM(wi.xi) <= W和xi = 0, 1（xi表示物品在袋子中或不在袋子中的状态）。

就我而言，条件和目标都存在细微差别：

  • 所有物品的重量为1，wi = 1, i = 1...n

  • 我总是想把一半的东西放在包里。因此，袋子的最大重量容量是物品数量的一半（四舍五入）。W = ceil[n/2]或W = floor[(n+1)/2]。

  • 此外，包内的重量必须等于其最大容量SUM(wi.xi) = W

最后，不是最大化包内物品的价值，而是目标是内部物品的价值尽可能接近外面物品的价值。因此，我的目标是minimize |SUM(vi.-xi) - SUM[vi(1-xi)]|，它简化为minimize |SUM[vi(2xi - 1)]|.

现在，在上面的 Wikipedia 页面中有原始 0/1 背包问题的伪代码（您可以在本文底部找到它），但我无法将其适应我的场景。有人可以帮忙吗？（我不是要代码，只是为了一个想法，所以语言无关紧要）

谢谢！

维基百科的 0/1 背包问题的伪代码：

假设w1, w2, ..., wn, W是严格的正整数。定义 为在重量小于或等于使用最多（第一个项目）的项目时m[i,w]可以达到的最大值。wii

我们可以m[i,w]递归定义如下：

  • m[0, w]=0
  • m[i, w] = m[i-1, w] if wi > w（新品超过当前重量限制）
  • m[i, w]= max(m[i-1, w], m[i-1, w-wi] + vi) if wi <= w.

然后可以通过计算找到解决方案m[n,W]。

// 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] := max(m[i-1, j], m[i-1, j-w[i-1]] + v[i-1])
        else:
            m[i, j] := m[i-1, j]
4

1 回答 1

2

感谢@harold，看来这个问题不是背包问题，而是分区问题。我正在寻找的部分伪代码在相应的维基百科页面中：https ://en.wikipedia.org/wiki/Partition_problem

编辑：实际上，分区问题算法告诉您一组项目是否可以分成两组相等的值。假设它不能，你有近似算法，它说你是否可以将集合分成 2 个集合，它们的值低于d. 但是，他们不会告诉你产生的子集，这就是我所寻求的。

我最终在这里找到了一个问题（这里：Balanced partition），并带有一个我已经测试过并且工作正常的代码示例。

于 2016-01-29T17:18:33.283 回答