在整数数组中找到与给定数字求和的最小集合
给定sum和一个正整数数组，找到其元素加起来为s的最小子集。 例如，给定数组{1,2,3,4,5}和sum s = 8，最小子集将是{3,5}。
到目前为止，我可以使用递归来解决使用贪婪方法添加到数组的一组整数，但是我找不到如何找到最小子集。 我应该研究一个特定的算法吗？
这是“零一平等背包问题”。 它是NP完全的。 但是，存在针对该问题的各种有效算法。
-
如果总和足够小以分配那么多位的内存并迭代它们n（数组元素的数量）次，则可以使用动态编程。
-
像CPLEX，Gurobi和SCIP这样的混合整数程序解算器通常会在可能在实践中出现的“典型”实例上做得相当好。 在制定背包问题时需要注意作为MIP求解器的输入以避免精度问题。
-
如果你可以忍受一些不精确的： 不等式背包的多项式时间近似方案 （你想要最小的数字总和最多的那个），并且不难描述：将所涉及的所有数字缩放到某个东西您可以在哪里进行动态编程并处理结果。 如果您注意接受近似问题的近似解决方案，您可以使用相同的方法来获得平等背包的近似解决方案。