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

Question

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

到目前为止，我可以使用递归的贪婪方法来解决一组整数相加到数组中的问题，但我不知道如何找到最小子集。我应该研究特定的算法吗？

Answer 1

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

1. 如果总和足够小，足以分配那么多位内存并对其进行迭代 n(数组元素数)次，则可以使用 dynamic programming.

2. Mixed-integer program CPLEX、Gurobi 和 SCIP 等求解器通常在实践中可能出现的“典型”实例上表现得相当好。将背包问题表述为 MIP 求解器的输入时需要小心，以避免出现精度问题。

3. 如果您可以容忍一些不精确:Polynomial-time approximation schemes对于不等式背包(您希望最小的一组数字总和最多为 s)存在并且不太难描述:将涉及的所有数字缩小到可以进行动态处理的值编程并处理结果。如果您也注意接受近似问题的近似解，则可以使用相同的方法获得等式背包的近似解。