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

Question

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

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

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

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

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

Answer 1

无论这是否是 NP-hard，您都可以使用易于访问的整数编程软件有效地解决您需要的问题实例。对于您的问题，您可以定义 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中的lpsolve或lpSolveAPI包或intlinprog 在 MATLAB 中的函数。