我正在开发一个解决 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. Definem[i,w]
to be the maximum value that can be attained with weight less than or equal tow
using items up toi
(firsti
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]
最佳答案
感谢@harold,看来这个问题不是背包问题,而是分区问题。我正在寻找的部分伪代码位于相应的维基百科页面中:https://en.wikipedia.org/wiki/Partition_problem
编辑:好吧,实际上,分区问题算法会告诉您一组项目是否可以分成 2 个等值的集合。假设它不能,你有近似算法,它说你是否可以将集合分成 2 个集合,它们的值的差值低于 d
。 .
但是,他们不会告诉您结果子集,而这正是我一直在寻找的。p>
我最终在这里找到了一个问题(此处:Balanced partition),其中包含一个我已经测试过并且工作正常的代码示例。
关于algorithm - 背包的变体,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35088778/