algorithm - 背包的变体

Question

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

这里描述了原始问题:https://en.wikipedia.org/wiki/Knapsack_problem .万一以后链接丢了，我给大家总结一下0/1 Knapsack problem(如果你熟悉，请跳过这一段):假设我们有 n元素，每件都有重量 wi和值(value)vi .我们想把元素放在一个能承受最大重量的袋子里 W ，这样袋子里的总值(value)是在不超重袋子的情况下可能的最大值(value)。项目不能有多个实例(即，我们每个实例只有一个)。问题的目标是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

最后，目标不是最大化袋内元素的值(value)，而是袋内元素的值(value)尽可能接近袋外元素的值(value)。因此，我的目标是 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)，其中包含一个我已经测试过并且工作正常的代码示例。