java - 在整数数组中找到给定数字和的最小集合

Question

给定总和 s 和一个正整数数组，找到其元素加起来为 s 的最小子集。例如，给定数组 {1,2,3,4,5} 和总和 s = 8，最小子集将是 {3,5}。

到目前为止，我可以使用递归的贪婪方法求解一组整数，这些整数加起来是数组，但我找不到如何找到最小子集。我应该研究一个特定的算法吗？

Answer 1

这就是“零一平等背包问题”。它是NP完全的。然而，存在多种有效的算法来解决这个问题。

1. 如果总和足够小以分配那么多位的内存并对其进行 n（数组元素的数量）次迭代，则可以使用动态编程。

2. CPLEX、Gurobi 和 SCIP 等混合整数程序求解器通常在实践中可能出现的“典型”实例上做得相当好。在将背包问题公式化为 MIP 求解器的输入时，需要注意避免精度问题。

3. 如果您可以容忍一些不精确性： 不等式背包的多项式时间近似方案（您希望最小的一组数字总和最多为 s）存在并且不难描述：将所有涉及的数字缩小到某个值您可以在其中进行动态编程并处理结果。如果您也注意接受近似问题的近似解，则可以使用相同的方法来获得等式背包的近似解。