在整数数组中找到与给定数字相加的最小集合 [英] Finding the Minimal Set That Sum to a Given Number in an Array of Integers
问题描述
给定总和 s 和一个正整数数组，找到元素加起来为 s 的最小子集.例如，给定数组 {1,2,3,4,5} 和总和 s = 8，最小子集将为 {3,5}.
Given the sum s and an array of positive integers, find the minimal subset whose elements add up to s. For example, given the array {1,2,3,4,5} and the sum s = 8, the minimal subset would be {3,5}.
到目前为止，我可以使用递归的贪婪方法来求解 a 一组整数，这些整数相加到数组中，但我找不到如何找到最小子集的方法.是否有我应该研究的特定算法?
So far I can solve for a set of integers that add up to the array with the greedy approach using recursion, but I can't find how to find the minimum subset. Is there a specific algorithm I should research?
推荐答案
这是零一平等背包问题".它是NP完全的.然而，针对该问题存在多种有效算法.
This is the "zero-one equality knapsack problem." It is NP-complete. However, a variety of effective algorithms for the problem exist.
如果总和小到足以分配这么多位的内存并迭代它们 n(数组元素的数量)次，您可以使用 动态编程.
混合整数程序 CPLEX、Gurobi 和 SCIP 等求解器通常会这样做在实践中可能出现的典型"实例上相当不错.将背包问题公式化为 MIP 求解器的输入时需要注意一些问题，以避免出现精度问题.
Mixed-integer program solvers like CPLEX, Gurobi, and SCIP will often do fairly well on "typical" instances that are likely to arise in practice. Some care needs to be taken when formulating knapsack problems as input to MIP solvers to avoid precision issues.
如果你能容忍一些不精确:多项式时间近似方案不等式 背包(您希望最小的一组数字总和最多为 s)存在并且不太难描述:将所有涉及的数字缩小到可以进行动态编程的地方并处理结果.如果您也注意接受近似问题的近似解，则可以使用相同的方法来获得等式背包的近似解.
If you can tolerate some imprecision: Polynomial-time approximation schemes for inequality knapsack (where you want the smallest set of numbers summing to something at most s) exist and aren't too hard to describe: Scale all of the numbers involved down to something where you can do dynamic programming and deal with the result. You can use the same approach to get approximate solutions to equality knapsack if you take care to accept near-solutions to the approximate problem as well.
这篇关于在整数数组中找到与给定数字相加的最小集合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
