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

[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

]

[hsfzxjy]

数据量有多大？这决定你能接受的时间复杂度下限

[jetvster]

先分组，再递归，复杂度应该不高

[wzy44944]

问下做人工匹配的人有什么经验？

[ZRS]

变种传输问题，不会有复杂度很低的解法。建议从业务方向入手

[CEBBCAT]

根据楼主的描述，好像不存在唯一解。楼主清楚的吧？

[diandian666]

@totatx 这个地址的需求和我的还是有区别的。我这需求的是需要数组 2 全部用上且只用 1 次匹配数组 1.

[diandian666]

@maggch97 大佬尝试一下？

[jukka]

仔细想了下，不太对，这里没有状态转换，数据量不大单纯的暴力搜索应该能出结果，想复杂了。

[betatabe]

人工匹配的算法不就是现成的算法吗，直接问问咋匹配的不就指导了（指数复杂度的算法，人工几分钟算出来只能说有丶东西）

[diandian666]

@hsfzxjy 线上运行的时候，直接就发现数组 2 的数据有 80+个。组 1 也有十个左右。我合并了组 1 相关的，才变成几个

[diandian666]

@betatabe 我刚还真去问了为啥这么快就能匹配。他们说随便看看就匹配出来了，无规则....

[diandian666]

@jukka 数组 1 大概 10 个以内。数组二 100 个以内。这样的规模

[betatabe]

@diandian666 第一个例子这种随便看看匹配出来？

[maggch97]

@hsfzxjy 我给你个写法思路吧，把第二个数组修改成[[value1, count1], [value2, count2], ... ], 把相同的数字合并在一起。dfs 的时候去枚举 count

如果你 1 也有重复，也能减枝。不过我觉得我上面说的对于你这个数据量完全够了

[jiangzm]

你的这些数字是有特征的， 所以前面有同学说走业务方向参考人工经验是对的。
再加上一些历史组合优先考虑， 应该能降低一点复杂度和计算量

[jiangzm]

@betatabe 小看了人工的历史经验

[diandian666]

@akaHenry 大佬的回答。我也是根据大小先倒序。从数组 1 最大的开始匹配数组 2 最大的开始。数组 2 一直往下加，超出数据就剔除。最终也是能实现上面题目末尾的两组数据。原题的那组失败了，因为原题那组需要剔除中间的值，这个剔除超乎我的想象，数据太大了

[jaggle]

B 中的数字能有剩余吗？

[MMMMMMMMMMMMMMMM]

你与业务团队大概是信息不对称

他们能人工匹配出来，说明可能有订单相关的 id 之类（根据 id 反查直接已经有结果列表了，然后人工加总而已）

你在做的很可能是无用功，去问问吧

[diandian666]

@jaggle 不可以，要全部使用。因为数组 1 的总和刚好等于数组 2 的