python - 给定一个长度数组，找到最接近总长度的组合

Question

我有两组变量，一组静态的段长度数组和一个由用户指定的动态最终总长度。

例如，数组 lengths = [50,40,80,30,108,25]，total = 150。

我将如何计算长度数组值的最佳组合以尽可能接近指定的总数？仅使用加法。因为我们使用指定长度的段来尽可能接近目标长度。

并非所有数组值都必须使用。每个数组元素都可以无限次使用，但我们希望使用尽可能少的数学运算得到最终结果(即不想做 25+25，而不是仅仅使用 50)

Answer 1

这个问题是 NP 难的，因为 subset sum problem 的一个 NP 完全变体可以减少到它。不同之处在于集合的元素可以多次使用。它也可以被视为 change-making problem 的变体。 ;见this question on cstheory.SE了解详情。

如果存在总和正好等于总和的组合，那么这就是最优解，因此您的算法会找到它。相反，如果没有这样的组合，您的算法将找到具有不同总和的解决方案；不同的组合是最优的这一事实将证明没有子集完全等于总和。

因此，由于您的问题是 NP-hard 问题，这意味着没有已知的算法可以给出准确的答案并且还可以有效地扩展到大输入。如果您需要一种能够找到真正最优解的算法，那么您不会比某种 backtracking search 做得更好。 .否则，如果“足够好”足够好，值得一读 heuristic algorithms对于子集和问题，它可能会以直接的方式适应您的问题。