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

[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

]

[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 问题