背包的变体

Question

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

原来的问题描述在这里：https://en.wikipedia.org/wiki/Knapsack_problem。以防以后link不见了，我给大家总结一下0/1 Knapsack problem（熟悉的可以跳过这一段）：假设我们有 n 个项目，每个项目的重量 wi 和价值 vi。我们想把物品放在一个袋子里，它支持最大重量 W，这样袋子里的总价值是最大可能的，而不会使袋子超重。项目不能有多个实例（即，我们每个实例只有一个）。问题的objective是maximize SUM(vi.xi)使得SUM(wi.xi) <= W和xi = 0, 1（xi表示物品在包里或不在包里的状态）。

对于我的情况，两种情况都存在细微差别 objective:

所有物品的权重为1，wi = 1, i = 1...n
我总是想把一半的东西放在包里。因此，包的最大重量容量是物品数量的一半（四舍五入）。W = ceil[n/2] 或 W = floor[(n+1)/2]。
此外，包内的重量必须等于其最大容量SUM(wi.xi) = W

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

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

谢谢！

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

Assume w1, w2, ..., wn, W are strictly positive integers. Define m[i,w] to be the maximum value that can be attained with weight less than or equal to w using items up to i (first i items).

We can define m[i,w] recursively as follows:

m[0, w]=0

m[i, w] = m[i-1, w] if wi > w (the new item is more than the current weight limit)

m[i, w]= max(m[i-1, w], m[i-1, w-wi] + vi) if wi <= w.

The solution can then be found by calculating 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]

Answer 1

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

编辑：好吧，实际上，分区问题算法会告诉您一组项目是否可以分成 2 组相等的值。假设它不能，你有近似算法，它说你是否可以将集合分成 2 个集合，它们的值的差值低于 d。但是，他们不会告诉你结果子集，而这正是我要找的。

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

背包的变体

Variant of Knapsack

algorithm

pseudocode

knapsack-problem

partition-problem