这是一个创建于 2716 天前的主题，其中的信息可能已经有所发展或是发生改变。
问题：有一组 float 型数值（设为 500 个），设目标值 goal 为 2000000 ，若单个数值不能拆分，如何求出数组中任意个数数值之和最接近 goal 的一组数值组合？？
尝试：先删除数组中大于 goal 的所有数值（减少运算量），用 python 的 itertools.combinations 来生成任意个数数值的所有可能组合，逐个求和并过滤掉总和大于 goal 值的组合，最后 max 得出结果
失败：然而想法是好的，上述尝试生成的组合可能超过百亿，运行几十秒直接“ Memory Error ”
难点： 需要求出最接近 goal （而非等于）的一个组合，是不是意味着必须穷举所有可能？？
 |
1
faketemp OP #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 友有何高见？？？？ |
 |
2
SingingZhou 2016-11-20 15:57:41 +08:00 via iPhone
唔，其实你不需要把所有的不同组合都保存下来，你保存一个最接近的就好了，这样就不会超内存了…不过这样仍然是一个很慢的算法
可以考虑用类似背包的动态规划，复杂度 2000000×500 左右，会快一些，但是内存占用比较大 暂时没啥特别好的想法 |
 |
3
GtDzx 2016-11-20 16:03:32 +08:00
如果是整数，并且 goal 不很大的话，可以时间 O(goal * N)、空间 O(goal)的 DP
float 没有办法用上面的 DP |
|
4
faketemp OP @SingingZhou 谢答！只是不计算所有组合的和，如何判断哪个才是与 goal 值“最接近”的呢？？
如果某组合的和正好等于 goal 则结束运算即可，只是这种几率过小了(⊙﹏⊙)b …… 所以才需要算出全部和，最判断找出“最接近”——这个算法很笨，确实我想得起的唯一 一个办法…… |
|
5
SingingZhou 2016-11-20 16:09:05 +08:00 via iPhone
@SingingZhou 傻了…发现是 float
|
 |
6
wy315700 2016-11-20 16:10:22 +08:00
01 背包问题
|
|
7
SingingZhou 2016-11-20 16:10:30 +08:00 via iPhone
@faketemp 我的意思是你只需要保存最接近的那个组合，如果新的组合更接近 goal 的时候，再更新这样？
|
|
8
faketemp OP |
|
9
SingingZhou 2016-11-20 16:18:39 +08:00 via iPhone
@faketemp 看了看代码，发现是一次性生成所有可能的组合，那确实会比较慢…我觉得如果自己写 dfs ，然后加点最优性剪枝应该能快些，也不至于内存不足这样……
|
 |
10
publicID002 2016-11-20 16:34:51 +08:00 via Android
看样子乘 100 就变整数了吧，那样就可以用上面说的 DP 做了
|
 |
11
v9ox 2016-11-20 17:19:24 +08:00 via iPhone
这不就是 leetcode 的 K sum 嘛
复杂度 n^(K-1) |
 |
12
starqoq 2016-11-20 18:59:41 +08:00
你可以尝试全部四舍五入变成整数，然后按照 01 背包做，最后取前后的 250 个结果（因为计算误差最多这么多）做精准计算。但是这样依然可能会有较小的的误差。例如两个方案的和只差 0.1 ，那么就无法准确地找到较好的那个方案。
准确解应该没有办法在多项式内找到。毕竟有小数的话，状态空间会很大。 |
 |
13
ipwx 2016-11-20 19:43:43 +08:00
|
|
15
faketemp OP @sensui7 没错，合适的组合可能是一个数值，也可能是 487 或 35 个数值之和——因为数组 numarray 是用户输入的，无法确定个数和规律
K sum 问题中 K 是确定的，我们的需求中 K 并不确定 这是不是最终又回到了“穷举组合”这条路？ 不过 01 背包和 K sum(closest)算法与我们需求近似，需要再仔细研究开开脑洞\(^o^)/~ |
 |
16
htfy96 2016-11-20 22:00:06 +08:00
如果不一定要最优解的话，可以尝试下遗传算法
|
|
17
faketemp OP @starqoq 如果如 @publicID002 所说将数组值全部乘 100 变成 int 型，然后按 01 背包来做 复杂度是否能够接受？
@v9ox 由于 K sum 中的 K 值无法确定，理论上的解法是不是应该以次进行 2 sum(closest)/3 sum(closest)/4 sum(closest)…… len(numArray) sum(closest)，最终才能得到最优组合的答案？？ 有没有更高效或巧妙的解法呢？ |
|
18
v9ox 2016-11-21 09:19:47 +08:00
@faketemp 我觉得对于 k sum (closest), stephan 那群人讨论了半天, 得到的最优就是 N^(k-1), 那么对于 k 不确定, 只能一个一个加了. 不过即使是这样, 复杂度依旧是 N^(k-1), 低次项不用考虑嘛.
|
 |
19
srlp 2016-11-21 12:59:31 +08:00 via iPhone
|
|
20
v9ox 2016-11-21 13:37:45 +08:00
O(N^1 + N^2 + N^3 + ... + N^k) = O(N^K)
为啥会是 O(n^n) 或者 O(n!)啊? |
|
21
faketemp OP @v9ox 看来只有穷举 k 值然后分别计算更新 k sum(closest) 了 不知道这个复杂度是否可行 研究研究先
|
|
22
faketemp OP @v9ox @srlp @SingingZhou @starqoq ……
经过研究， 穷举 k 值来计算 k sum(closest) 的方法不可行(＞﹏＜) 搜索了很多解法发现最多提到 4 sum ，而且没有一个通用的穷举计算 k sum 的解法 k 每增加一就要增加一层循环 无法想象如果 k=300 时…… 所谓“以空间换时间”的解法也不可取 比如仅仅 500 个数取 4 个的组合最少都有几亿种，更别提要穷举任意个数的组合了—— 32G 内存估计也耗尽 目前这个问题基本无解(；′⌒`) 感谢大家的想法和讨论 希望若干年后某神人能关注到这个问题了…… |
|
23
starqoq 2016-11-24 20:58:11 +08:00
如果你的确需要穷举所有组合的话，复杂度大约是 O(2^N)，在 N = 20 的情况大约需要 1s 计算。
背包问题能解是因为状态空间有限，只需要记录前 i 个物品能否组成 w 重量的组合就可以了。而重量都是整数，所有重量的可能性就是 0 到目标值。 但小数就不一样了，状态空间是连续的，即使仅记录可达状态，状态的增长也会很快。所以就只能用近似的方法来减少状态空间。只能求得多项式复杂度下的近似解。 你可以参考一下算法导论中的 动态规划问题 。 在图灵机上，以后也没有解。 |
Select Language