algorithm - 如何将 N 个数字分配到 M 包中以最小化某些目标函数？

Question

我有 N（例如 30）个整数V[i]和 M（例如 8）个包，每个包都有一个期望值P[j]。

我想将每个整数分配给一个包，以下表达式计算 pack 中的总和与V[k]packj的期望值之间的差j。

diff[j] = abs(P[j] - sum(V[k] that in pack j))

目标是找到最小化的最佳解决方案sum(diff[j])。

我不知道这种问题的类型是什么。这可以通过线性规划解决，还是 NP 完全问题？

Answer 1

无论这是否是 NP 难的，您都可以使用易于访问的整数编程软件有效地解决您需要的问题实例的问题。对于您的问题，您可以定义 x_{ij} 来定义是否将 X[i] 分配给组 j。然后，您还可以定义变量 d_j，它们是公式中的 diff[j]。那么你的模型是：

min_{x, d} \sum_{j=1}^M d_j
s.t.       d_j >= P[j] - \sum_{i=1}^N X[i]x_{ij} \forall j
           d_j >= \sum_{i=1}^N X[i]x_{ij} - P[j] \forall j
           \sum_{j=1}^M x_ij = 1 \forall i
           x_{ij}\in \{0, 1\}

这是一个混合整数优化模型，例如，可以使用 R 中的lpsolveorlpSolveAPI包或intlinprogMATLAB 中的函数来求解。

Answer 2

我可以通过将另一个 NP 问题减少到这个问题来证明你的问题是 NP。换句话说，我将证明，如果我能回答这个问题，我就能立即回答另一个 NP 问题。

我要减少的具体问题是子集和问题：

让V是一组数字。我们想知道是否sum(V)==0。让P={0}（一个长度为一的数组只包含0）。sum(diff[j])==0在这种情况下，当且仅当子集总和为 时，您的问题的最佳解决方案是0。换句话说，子集和问题是你的问题的一个特例，所以你的问题至少和子集和问题一样难。

因此，您的问题是NP。我仍然不确定它是否是NP-Complete。

Answer 3

通过从2 分区(2P)减少，这是 NP 难的。将当前问题更改为询问 sum(diff[j])=0 的决策问题。给定一个 2P 的实例，让P[0] = P[1] = sum(V)/2. 如果存在两个分区，那么显然存在一些与sum(diff[j])=0.

有一个用于 2 分区的伪多时间算法，但它不太可能适用于这个问题，因为它不适用于 >=3 分区。

看起来这类似于装箱，但我不能 100% 确定，因为你可以溢出“包装”而不是“垃圾箱”。