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

[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

]

[ih8es9OIzne0959p]

我也不会，大家觉得和”田忌赛马“的剪枝法那个思路沾边吗

[ih8es9OIzne0959p]

楼主是暴力递归吗，可以加一些判断条件，先算出来 1 组中第一项对应的数据，假如 1 组中的第一项数据对应的第二组数据只有一种情况可以直接 ruturn ，意思就是分治法一次别算到底分组算，分步+分组。

[ih8es9OIzne0959p]

@ajaxgoldfish return

[ih8es9OIzne0959p]

既然人工对出来这种方法也能跑出来，这就是人工的那个思路，先算 1 组中第一个数据对应的集合。然后再算第二组的。第一组如果有多种可能的话那就再跑第二组。前提是跑第一组的数据和第二组是一样的，不用剔除第一组选中的数据，剔除就麻烦了，就涉及到回溯法了。这样分组跑后边再判断

[ih8es9OIzne0959p]

这样程序第一步时间复杂度就直接是 n 。。。。搬个板凳听下面大佬的更好的方法。最近也有类似需求

[jimliang]

背包问题的变种。

[penzi]

我错了，这个数据量随机的话减枝搜+DP 复杂度也是爆炸的

我要吐槽一下，你给的第一组数据是错的。数组 1 的和和数组 2 的和差了 0.01

上面有人给出了 python 代码，直接数组 2 里面每次取最大的去凑数组 1 里面最小的数字。我怀疑你们的数据全都是这个策略就能有解的。

[penzi]

@maggch97 我写了一堆代码，发现结果全都是按照上面的策略就有解，你不妨多贴一点数据出来验证一下

[penzi]

@maggch97 看错了，数据没有错。我取*100 取 int 的时候被被舍掉了 1

[penzi]

@wxf666 int(1.15*100) == 1.14

[timjuly]

这两组数据都是有根据出来的，绝对能匹配成功
------
既然有根据，为啥不让上游出数据的时候给你分好组，上游比你有更多的办法解。

[2NUT]

显然你的抽象没有利用足够的业务信息

[wxf666]

@maggch97 确实，改成 round(1.15 * 100) 就能继续跑了

但跑了快半个钟了，还没出结果。。

[penzi]

@wxf666 https://maggch97.github.io/dfs/dfs.html 你要跑的话可以试试我这个 js 写的，至少楼主给的几个数据都能出结果

[iOCZ]

这是一个组合问题，但是没有明显能快速收敛的条件。

[mochen666]

题主，小弟刚才人工算了一下，你看结果是不是比你给的运算量小。
我的思路是从数组 1 中最小得数 a 开始，用数组 2 中比 a 小得数从前往后开始求和
17.76>=5.88+5.04+3.64+2.8
26.67>=3.45+3.36+2.8+2.52+2.24
62.13>=数组 2 剩下得那一串串
能否给你点启发

[TongNianShanHe]

楼上的大佬们也说过了这是 NP 问题，直接用动态规划或者剪枝啥的。。。数据量小可以，数据量大除非你租个天河（
我这边斗胆开个脑洞：不死钻这两组数据，既然这组数据是一组实际的下单和退单数据，那么肯定有时间吧，根据时间进行排序，然后再用 KMP 或者滑动窗口试试？（不一定对，如有误还请指正）

[Xs0ul]

1. 虽然大佬提了这是 NP 问题，如果两组数据全随机复杂度爆炸。但从楼主给的例子来看，数组 2 显然有很多小的而且重复的数字，转化成(value, count)能让暴力搜索的复杂度减少很多
2. 实践上来说，或许可以考虑设置一个 timeout ，1 分钟没搜出来就交给人工

[nuk]

是算财务的吧？以前写过类似的，就是背包问题，数据量多的话基本没法求解，只能循环遍历，财务经常抱怨程序运行了一天一夜也跑完。

[crab]

LeetCode 组合总和 可以看看。
之前转运合并包裹重量用这个算的。