算法求救：数组中任意 N 个数的和 最接近指定数值，详述见内……

[faketemp]

问题：有一组 float 型数值（设为 500 个），设目标值 goal 为 2000000 ，若单个数值不能拆分，如何求出数组中任意个数数值之和最接近 goal 的一组数值组合？？

尝试：先删除数组中大于 goal 的所有数值（减少运算量），用 python 的 itertools.combinations 来生成任意个数数值的所有可能组合，逐个求和并过滤掉总和大于 goal 值的组合，最后 max 得出结果

失败：然而想法是好的，上述尝试生成的组合可能超过百亿，运行几十秒直接“ Memory Error ”

难点： 需要求出最接近 goal （而非等于）的一个组合，是不是意味着必须穷举所有可能？？

[faketemp]

@v9ox 看来只有穷举 k 值然后分别计算更新 k sum(closest) 了 不知道这个复杂度是否可行 研究研究先

[faketemp]

@v9ox @srlp @SingingZhou @starqoq ……
经过研究， 穷举 k 值来计算 k sum(closest) 的方法不可行(＞﹏＜)
搜索了很多解法发现最多提到 4 sum ，而且没有一个通用的穷举计算 k sum 的解法
k 每增加一就要增加一层循环 无法想象如果 k=300 时……

所谓“以空间换时间”的解法也不可取
比如仅仅 500 个数取 4 个的组合最少都有几亿种，更别提要穷举任意个数的组合了—— 32G 内存估计也耗尽

目前这个问题基本无解(；′⌒`)

感谢大家的想法和讨论
希望若干年后某神人能关注到这个问题了……

[starqoq]

如果你的确需要穷举所有组合的话，复杂度大约是 O(2^N)，在 N = 20 的情况大约需要 1s 计算。
背包问题能解是因为状态空间有限，只需要记录前 i 个物品能否组成 w 重量的组合就可以了。而重量都是整数，所有重量的可能性就是 0 到目标值。

但小数就不一样了，状态空间是连续的，即使仅记录可达状态，状态的增长也会很快。所以就只能用近似的方法来减少状态空间。只能求得多项式复杂度下的近似解。

你可以参考一下算法导论中的 动态规划问题 。

在图灵机上，以后也没有解。