查找整数数组中给定数值的最小集合

Question

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

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

Answer 1

这是“零一平等背包问题”。这是NP完整的。然而，存在多种有效的算法。

1. 如果总和小到足以分配的存储器，许多位和在它们之间迭代N（数组元素的数）倍时，可以使用dynamic programming.

2. Mixed-integer program解算器等CPLEX，Gurobi，和SCIP通常会在实践中可能出现的“典型”情况下做得相当好。在将背包问题作为MIP解算器的输入时，需要注意一些问题以避免精确性问题。

3. 如果你能容忍一些不精确：Polynomial-time approximation schemes为不平等背包（您想最小的一组数字，在将多数总结的东西）的存在，是不是太难形容：规模涉及的所有号码直到您可以执行动态编程并处理结果。如果您注意接受近似问题的近似解，也可以使用相同的方法获得近似解背包背包。