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

[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

]

[jiangzm]

@wangnimabenma 逗笑我了

[zxcslove]

感觉和库存棒材的切割优化方案很像

[jukka]

典型的背包问题。搜 背包九讲， 看下哪个合适你的场景。

[SimonOne]

数组 1[1,2]
数组 2[0.1,0.2,0.3,0.7,0.8,0.9]

按你的匹配法有多个解，你想哪个呢？

[jiangzm]

@diandian666 反推成功也不一定是真实的组合， 不太明白你们用这个意义在哪。 还有从亚马逊运营数据为啥两份数据没有共同的标识关联。

[diandian666]

@SimonOne 只要其中一个解就行了。不用全部解

[lakehylia]

你这不就是简化成从一堆数据里面挑出 N1 个数，使和为 A1 ，然后把剩下的数挑出 N2 个数，使和为 A2 。如果中间失败了，就剪枝

[diandian666]

@jiangzm 不知道呢，一组数据是付款订单。另一组数据是移除订单。反正就是这两个不互通。需要自己匹配关联呢。

[diandian666]

@lakehylia 是这个道理。道理懂了，代码拉了，尴尬。

[diandian666]

@zxcslove 嗯嗯嗯呢。

[SimonOne]

用遍历感觉会死，比如
数组 1[1,2,3]
数组 2[01,0.9,1.9,2.1,0.2,0.8]

用遍历的话，出来 1=0.1+0.9 ，结果后面 2 和 3 就遍历不出来了 😂

[diandian666]

@SimonOne 这就要重新算了。也难道我了。遍历，递归，剔除 都用了。我最后也只能匹配后面举例的两组数据，原题的那组没成功。知道问题在哪里，但是写不动了...

[diandian666]

@jukka 搜嘎，写基础代码久了，很多没都没听过。我去了解了解... ~~~///(^v^)\\\~~~

[maggch97]

这点数据量，搜索+减枝呗，搜不出来是你写错了。又不用考虑出题人会给一万个 0.01 数据。

[maggch97]

@jukka 这是典型的背包？

[totatx]

https://leetcode.cn/problems/coin-change/

[akaHenry]

你这运营数据有点意思.

你可能需要使用 python + pandas 之类的工具, 来写个统计+计算脚本, 可能很快.

提供一个粗糙的思路:

1. 2 组数据, 先排序(小<大).
2. 数组 2 数据, 计算一些特征值(暂存):
重复值先 count 计数, 并 sum() 部分值.
计算数组 2 的 均值, 众数. 并作为后续遍历的结束条件.

3. 因为数组 1, 是由 数组 2 构造的. 比如 17.76, 必然由 < 17.76 的数组合成(废话). 遍历时, 可以剔除 > 17.76 的值.
结合 二分法 + 遍历, 应该不需要完全遍历.

数组 1 排在前面的计算结果, 也是 后面的值的一部分.

按照这个思路, 应该可以写一个能用的算法. 哈哈

[diandian666]

@jukka 看了 背包九讲 9 个例子都和我的需求不一样呢...继续求高人指点...

[SimonOne]

@akaHenry #36 😂 幸好是订单，值肯定是正数(至少是非负数)，不然遍历时还不能剔除 > 17.76 的值

[jukka]

不是完全一样的，背包去掉 cost ，weight 不取 max ，去相等，就是你这个问题了吧