十年程序员难倒了一个算法上面，真的老了

[diandian666]

如题，各位大佬摸鱼的时间看看怎么解决！！感谢！ 感恩！思密达！

公司业务需要，把我难倒了。各位大佬看看能不能摸鱼的时间来看看这个需求。代码递归跑的内存都溢出了，万分感谢。

题目：

有两组数字数组数据，数组 1 的数据的总和 = 数组 2 数据的总和。数组 1 的数量 <= 数组 2 的数量。且数组 1 中每一个数字都可以对应数组 2 中 N 个数字的和。找出数组 1 中的数字对应数组 2 中的数据。不能重复使用。 注：不用担心匹配不上的情况，这两组数据都是有根据出来的，绝对能匹配成功，之前都是人工匹配的，现在想用代码直接取代人工。

题目说的有点不清楚，举例：

数组 1： [62.13,26.67,17.76]

数组 2：[24.92,5.88,5.04,3.64,3.45,3.36,2.8,2.8,2.52,2.24,2.24,2.24,1.96,1.96,1.8,1.68,1.4,1.4,1.4,1.2,1.2,1.15,1.12,1.12,1.12,1.12,1.12,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.4,0.4,0.4,0.4,0.4,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28]

最终需要匹配出来结果

62.13=>[24.92,5.88,5.04,3.64,3.45,2.8,2.8,2.52,2.24,2.24,2.24,1.96,1.2,1.2],

26.67=>[1.96,1.68,1.4,1.15,1.12,1.12,0.84,0.84,0.84,0.84,0.84,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.4,0.4,0.4,0.4,0.4,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28]

17.76=>[3.36,1.8,1.4,1.4,1.12,1.12,1.12,0.84,0.84,0.84,0.84,0.56,0.56,0.56,0.56,0.56,0.28]

上面就是匹配的结果。

我这边多提供两组数据供测试,下面的两组测试成功的话，再尝试上面提到的那组数据，毕竟上面那组数据多，影响测试

第一组：

数组 1 [52.7,8.96]

数组 2 [21.44,6.72,5.44,5.12,4.48,3.20,2.24,1.92,1.92,1.92,1.28,1.28,1.00,0.96,0.50,0.32,0.32,0.32,0.32,0.32,0.32,0.32]

第二组：

数组 1 [23.17,3.2,1.22,0.32]

数组 2 [7.36,4.16,3.20,1.69,1.28,1.28,0.96,0.96,0.90,0.64,0.64,0.64,0.50,0.50,0.32,0.32,0.32,0.32,0.32,0.32,0.32,0.32,0.32,0.32

]

[jaggle]

所以真的存在人脑能算，但是计算机算不出来的题目吗，2333

[betatabe]

所以肯定有额外的输入信息，被 op 忽略了，仅靠两个数组去求解复杂度就是指数级的

[diandian666]

@jaggle 估计人脑也是乱串算对的。代码也行的，我的代码问题也发现知道哪里有问题，但是没能还没找到突破

[jaggle]

@diandian666 哦，对，间接需求导致 B 中无剩余的数字

[jaggle]

应该是什么券包之类的场景吧，比如 系统今天发了 n 个 金额总计 x 元的券包，里面包含 x1,x2,xn....的券，求券和券包的对应关系（所以为什么不用关系型数据库！）

[jiangzm]

业务系统是会避免产生数据孤岛的， 大概率是你没找到关联信息， 从源头拿数据吧，不要从二贩子(业务人员导出的?)拿数据

[maggch97]

@diandian666 我回家有时间给你写个代码吧，这么多贴子居然全在扯淡

[aijam]

https://gist.github.com/czheo/b5c01a35ef192713fd83d0826fe6901d

[xuanbg]

首先，你这个数字只能用一次，所以不是全组合。这样组合数其实非常少。而且大于集合 1 里面的数字的组合可以直接排除，那组合数就更少了。
OP 你的逻辑肯定没有优化好，我估计递归深度应该不会超过集合 2 的个数的平方。

[meeop]

暴力穷举吧,既然人工能做到匹配,说明计算量不大,计算机一定能完成,不行堆机器
这个问题据我理解是没有 o(n^2)以下算法解的,可能可以通过动态规划优化下性能

这个其实就是素数分解,如果有快速算法解的话,非对称加密就被破解了

[weiwoxinyou]

看了一下测试数据，有很多相同的小数，然后你汇总的值有小数点尾数为奇数的，这就意味着如果一个大数+一个尾数为奇数的值必定来源于一个或多个奇数尾数值加和，这个可以作为优先匹配方法。
在匹配完所有尾数为奇数的数值完全匹配后，算数组一的两数差，由于每一个值与其余值差必定对应数组二中数字，这样可以凑出另一部分的数据。
剩下的可以直接穷举了

[jukka]

内存循环是 0-1 背包问题。
这个问题暴力搜索的话，应该是 2^n 复杂度，不是 n^2 。

[ywl19891989]

排序之后倒序走。从最小的开始。穷举应该也可以的

[Damn]

https://club.excelhome.net/thread-1584367-1-1.html

暴露年龄了。。

[xuanbg]

解题思路是这样的：
先将集合 1 排序，从最小的数字开始凑。能凑出来的就是一棵树的根。
然后每个根开始用剩下的数凑第二大的数，每个能凑出来的组合就是这个根下的第二层子节点。
以此类推，凑下一个数，所有的组合形成下一层子节点。
从如果凑的过程中遇到凑不出来的，那么这棵树就可以删掉了。

综上所述，树的高度等于集合 1 的数字个数，树的数量取决于能凑出几个组合。

[shyrock]

简单说就是遍历数组 2 ，把其中每一个数尝试分配到数组 1 的某一个框里面。分配完之后检查每个框的小计等不等于代表这个框的数字。

如果不做任何优化剪枝，纯暴搜的话时间复杂度是 O(m^n)?

[dallaslu]

既然人肉算法一定能求出结果……我有个不成熟的想法。

我们把这个问题做个比喻，有多只大小不一的瓶子，里面装着大小不一石子和水，水面与平口持平，现在把所有石子捞出来混在一起，让一只强迫症乌鸦把石子装回去。

把瓶子和石子按大小依次排列，先扔大石子，后小石子，保证过程中水不溢出，直到某个石子 X 没有瓶子可投，此时从瓶子捞出适量的石头 Y （体积大于等于瓶中剩余体积+X 的体积）直到把这个石子投进去，最终投完。

困难的部分在于“捞出适量的石头 Y”这一步，应当设定一些原则，比如尽量捞出被置换次数较少的石头，尽量选择 Y 数量少的瓶子，以避免石子的分配方案变化过少出现死局。

基于这些设定，即使最开始的一批大石头位置放错，导致未能求出解，也能被置换石头的过程修正。

[xuanbg]

@xuanbg 如果深度优先进行递归的话，只要能生成一棵高度等于集合 1 数字个数的树，你就已经找到解了。

[dallaslu]

@dallaslu 当然复杂度爆炸哈哈，如果程序在限定的尝试次数内跑不出结果，建议转交给人工队解决

[optional]

给个傻的方案吧：
假设左边数组为 M(m 个数字)，右边数组为 N(n 个数字)
第一步：右边数组有 2^n 个排列组合(0~n 个数字)，枚举排列这个组合，去掉和不在左边的组合（这一步左边可以直接做一个 set ，所以这一步复杂度有 2^n 。假设得到 K 个组合。
第二步：对 K 这个组合选择 m 个，这里是 C(m,n)个选型，继续枚举它，通过并查集剪掉包含重复数字的（这一步存在优化空间）
第三步：在第二部 C(m,n)就能找到结果了（如果存在）