algorithm - 如何通过添加数组元素获得最接近数字的值

Question

假设我有数字 20 和一组数字 n“例如，这里的 n 是 4”{7, 2, 9, 3}

我想知道我可以从单个元素或将数组中的多个元素加在一起得到的大于数字 20 的最接近值和小于 20 的最接近值。

我不确定我应该使用什么数据结构或算法

谢谢!

Answer 1

这被称为背包问题(好吧，您的问题略有不同，但这并不重要)。

如果数字的总和相当低(状态是总和，值是真还是假取决于这个总和是否可达)，您可以使用动态规划。这种方法的时间复杂度是 O(N * SUM)。

如果数组的元素数量很少，您还可以遍历所有子集并计算每个子集的总和(这需要 O(2^N * Poly(N))时间)。

如果元素个数很少，但又不是那么少，可以使用中间相遇的技巧，让之前的解稍微好一点(O(2^(N/2) * Poly(N )).