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

[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

]

[smallWang]

这排列组合也太多了吧 你 N 的范围有确定吗？ 人工作也挺痛苦的啊

[muchenlou]

好家伙，有点意思。下意识想到的是穷举

[diandian666]

@smallWang N 的范围不确定的。这花了我两天时间写。后面举例的两组数据自己本地测试都能匹配成功。放到线上一跑，就有其他的匹配不成功（原题那组匹配不成功），虽然自己也知道问题出在哪，但是还是不懂怎么写下去了...

[tusj]

人工匹配的老哥，是真的有点牛逼。这 N 也没个限制，人工一般要匹配多久？

[w88975]

举例的话, 建议你拿一些简单的数字, 这眼睛都看花了

[lambdaq]

好家伙，搁这在对账呢。。。

[diandian666]

@tusj 我前面也怀疑这人工怎么匹配。就原题那组，我匹配了 62.13 这个。剩下两个数字 26.67,17.76 我代码匹配不到。我发给他们人工匹配剩下两个数字。几分钟不到就给我匹配出来了。惊掉我下吧，不能发图，不然你们估计也惊掉下巴......

[dallaslu]

数据复杂了肯定存在不唯一的解……另外这是在凑发票吗？

[diandian666]

@w88975 简单的数据，自己都可以按规则弄点简单的。但是代码跑可以用我提供的那几组。

[quan01994]

第一感觉只能穷举啊 ， ，，，，

[zqxjoe]

@lambdaq 看起来还真像对账用的

[liyang5945]

你倒不如说下原始的需求

[pual]

二分图匹配，匈牙利算法

[wangnimabenma]

这个运营得是研究生吧，我大专生可做不了这个

[wfd0807]

循环×动态规划

[diandian666]

@lambdaq 这也可以说算是。他是匹配到了之后，用个字段关联起来的。相当于把数据关联起来。没有关联的字段。这也有运营的一个问题在这里。

[diandian666]

@wfd0807 这是什么操作。我也是循环，递归，最终还是发现问题解决不了...有空可以试下，当作自己的锻炼啥也行，帮助我这个准备被 IT 淘汰的也好。哈哈哈

[diandian666]

@dallaslu 不是凑发票。就是亚马逊运营的数据需要关联起来。

[diandian666]

@liyang5945 需求就是 两组数据。进行匹配呢，我得到的需求也是这样。只不过我能找到这两组数据，我提供出来而已。

[diandian666]

@pual 这好高级啊。听都没听过。擦....尴尬。大佬求教

[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 ，去相等，就是你这个问题了吧

[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 的

[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)就能找到结果了（如果存在）

[optional]

撤回：第二步开始错了，首先没必要用并查集，直接判断 index 是否冲突就行，另外判断是否全等左边的可以在修改下，等会想到了回复。

[yorkyoung]

import itertools as it
import numpy as np
a = [52.7,8.96]
b = [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]
c = {}
for i in range(len(a)):
for j in range(len(b)):
if j < i:
continue
else:
for d in it.permutations(a, i+1):
for e in it.permutations(b, j+1):
if np.sum(d) == np.sum(e):
print("a 集合中的元素{}的和为{},与 b 集合中的元素{}相等".format(list(d),np.sum(d),list(e)))

[AkashicRecords]

是个多背包问题的变体。
Timus 上的 1394. Ships. Version 2 ，基本上和 OP 的问题是完全一致的了，Tag 是 hardest problem ，所以完全不用灰心做不出来。
虽然没有直接的题解，可以看看评论区的讨论 https://acm.timus.ru/forum/?space=1&num=1394

[alalida]

考虑简单情况

1,2,3,4

3,7

那就有两个解了 3-1,2 7-3,4
或者 3-3 7-1,2,4

[aqqwiyth]

这个是从 总返利里面, 推算返利订单列表?

[optional]

@optional

假设左边数组为 M(m 个数字)，右边数组为 N(n 个数字)
第一步：右边数组有 2^n 个排列组合(0~n 个数字)，枚举排列这个组合，去掉和不在左边的组合（这一步左边可以直接做一个 set ，所以这一步复杂度有 2^n 。假设得到 K 个组合，并在判断过程中分组，分组键为他们的和，
得到一个 map ，注意这里它的 value 应存数字的下标，而不是数字本身，命名为 indexesBySum 。
第二步：得到上一个 map ，按照 value 的数量排序，从数量最小的 key 出发，再遍历一次，不过这里每个 key 都要选择一个，然后如果 value 里面的下标已经用过的话，就跳过这个组合，应该就能得到答案了，如果只要其中一个就提前 return 。

[alalida]

感觉这题没有多项式时间解

[optional]

这里估一下复杂度，看起来是 C(2^n,m) 嗯，复杂度可真高

[majormei]

@optional 我最开始也是一样的思路，看到第一个例子的数组长度 90 ，估计是没法跑起来了……

[akaHenry]

@aijam 68L, 已经给出了答案.

跑了一下示例数据, 没啥问题.

[WngShhng]

0-1 规划问题，用 lingo 很好解决，这个问题是假如两个数组分别是 A,B ，长度是 m,n ，那么，就是 mxn 的 0,1 矩阵的求解的问题，如果用 x(i,j) 表示第 i 行第 j 个的值（取值 0 或 1 ），那么约束条件就是
x(i, 0)B(0)+x(i, 1)B(1)+....+x(i,n-1)B(n-1)=A(i)
以及，x(0,j)+x(1,j)+...+x(m-1,j)<=1 （这是考虑 B 数组可能会有剩余的情况）
所以，只需要求出这个 mxn 的 0,1 矩阵 X 就可以，暴力的方式就是按照 mxn 的维度进行遍历，可以排序之后再加一层判断逻辑降低复杂度

[optional]

@majormei 所以是个傻的办法，第一步产生了大量的冗余计算，忽略它吧

[tiedan]

背包问题

[wxf666]

@aijam 为嘛我改成楼主第一组数据（最长的那组），跑不出结果呢？

显示：ans = {6213: [], 2667: [], 1776: []}

[frodez]

@diandian666 你看一下 83L 。

[PeterD]

leetcode 0322

[sarvatathagata]

不被难倒就怪了，这明显是 NP 完全的。不知道上面这些回复要自己造这么多表现一看就非常差的轮子是干嘛，人家 wiki 上已经写了那么多近似算法了，这已经是一个被研究得很多的问题了。https://en.wikipedia.org/wiki/Balanced_number_partitioning

[geelaw]

@sarvatathagata #97 应该强调是 strongly NP hard ，这可以排除对伪多项式时间（动态规划解背包这种算法）的期待。

[vance123]

第一眼 NP ，第二眼背包。已经不知道是第多少次看到有人问 NP 的问题了

[vance123]

当然，每次都有不少人试图用各种奇巧淫计解决 NP 问题