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

[faketemp]

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

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

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

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

[faketemp]

#Python 3.x
from itertools import combinations
from heapq import nlargest

def trans(szNum):
return szNum.translate(str.maketrans('','',',，"“”'))

goal =2000000
num = [2627958.99,1903995.67,3133207.37,1000626.65,1377193.42,389084.48,1445055.87,402488.74,2908761.03,1154304.95,1384296.51,895361.64,5769.90,215879.19,56482.19,517084.97,41702.36,539160.33]

[num.remove(i) for i,v in enumerate(num) if v > goal]
countNum = len(num)
dResult = {}
for j in range(1,countNum + 1):
tL = combinations(num,j)
dResult.update({k:v for k,v in zip(map(sum,tL),tL) if k<=goal})

print({k:dResult[k] for k in nlargest(5,dResult)})
--------------------------------------------------------------------------------------------
大概是上面这种伪代码（演示需要，未测试），只是这种穷举的算法在 num 超过 50 的情况下就会导致内存耗尽（更别说 500 个值参与运算了），即使使用 X64 Python ，也因计算量大导致时间过长——这种方法并不可取， V 友有何高见？？？？

[SingingZhou]

唔，其实你不需要把所有的不同组合都保存下来，你保存一个最接近的就好了，这样就不会超内存了…不过这样仍然是一个很慢的算法

可以考虑用类似背包的动态规划，复杂度 2000000×500 左右，会快一些，但是内存占用比较大

暂时没啥特别好的想法

[GtDzx]

如果是整数，并且 goal 不很大的话，可以时间 O(goal * N)、空间 O(goal)的 DP
float 没有办法用上面的 DP

[faketemp]

@SingingZhou 谢答！只是不计算所有组合的和，如何判断哪个才是与 goal 值“最接近”的呢？？

如果某组合的和正好等于 goal 则结束运算即可，只是这种几率过小了(⊙﹏⊙)b ……

所以才需要算出全部和，最判断找出“最接近”——这个算法很笨，确实我想得起的唯一 一个办法……

[SingingZhou]

@SingingZhou 傻了…发现是 float

[wy315700]

01 背包问题

[SingingZhou]

@faketemp 我的意思是你只需要保存最接近的那个组合，如果新的组合更接近 goal 的时候，再更新这样？

[faketemp]

@GtDzx 我试了，如果 num 总数在 20 个以内，答案是可以在几秒内算出，然后 num 超过 100 的话……

数值来自交易数据，几乎全部是 float 值

[SingingZhou]

@faketemp 看了看代码，发现是一次性生成所有可能的组合，那确实会比较慢…我觉得如果自己写 dfs ，然后加点最优性剪枝应该能快些，也不至于内存不足这样……

[publicID002]

看样子乘 100 就变整数了吧，那样就可以用上面说的 DP 做了

[v9ox]

这不就是 leetcode 的 K sum 嘛

复杂度 n^(K-1)

[starqoq]

你可以尝试全部四舍五入变成整数，然后按照 01 背包做，最后取前后的 250 个结果（因为计算误差最多这么多）做精准计算。但是这样依然可能会有较小的的误差。例如两个方案的和只差 0.1 ，那么就无法准确地找到较好的那个方案。
准确解应该没有办法在多项式内找到。毕竟有小数的话，状态空间会很大。

[ipwx]

https://zh.wikipedia.org/wiki/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98

[sensui7]

@v9ox 他这 500 个数字完全无规律的, 结果可能是一个数字, 也可能是 300 个数字, 复杂度应该是 500!

[faketemp]

@sensui7 没错，合适的组合可能是一个数值，也可能是 487 或 35 个数值之和——因为数组 numarray 是用户输入的，无法确定个数和规律

K sum 问题中 K 是确定的，我们的需求中 K 并不确定 这是不是最终又回到了“穷举组合”这条路？
不过 01 背包和 K sum(closest)算法与我们需求近似，需要再仔细研究开开脑洞\(^o^)/~

[htfy96]

如果不一定要最优解的话，可以尝试下遗传算法

[faketemp]

@starqoq 如果如 @publicID002 所说将数组值全部乘 100 变成 int 型，然后按 01 背包来做 复杂度是否能够接受？

@v9ox 由于 K sum 中的 K 值无法确定，理论上的解法是不是应该以次进行 2 sum(closest)/3 sum(closest)/4 sum(closest)…… len(numArray) sum(closest)，最终才能得到最优组合的答案？？


有没有更高效或巧妙的解法呢？

[v9ox]

@faketemp 我觉得对于 k sum (closest), stephan 那群人讨论了半天, 得到的最优就是 N^(k-1), 那么对于 k 不确定, 只能一个一个加了. 不过即使是这样, 复杂度依旧是 N^(k-1), 低次项不用考虑嘛.

[srlp]

@v9ox

k 的可能性是 1 到 n ，所以穷举 k sum 的 k 的话，实际上是 O(n^n) 或者 O(n!)，实际上和穷举所有组合的复杂度等价。

[v9ox]

O(N^1 + N^2 + N^3 + ... + N^k) = O(N^K)
为啥会是 O(n^n) 或者 O(n!)啊?

[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 到目标值。

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

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

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