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

[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

]

[superhxl]

楼主数组 2 数据看似挺多，但实际上有很多重复的，所以先统计出数据项及个数。然后采用数学规划的方法，建立一个整数规划模型，直接调用开源求解器求解肯定比自己写算法快！个人看法

[optional]

@superhxl 呵呵，整数规划，你倒是说说这个约束怎么写

[dayeye2006199]

LZ 不是你老了。这个是一个典型的 NP complete 问题。
动态规划不好处理这类问题，因为会受到维度诅咒（状态的维度太高）。

这类问题一般就是几种搞法：
1. 精确解法 -- 把问题建模成一个整数规划（ https://en.wikipedia.org/wiki/Integer_programming ）或者约束规划（ https://en.wikipedia.org/wiki/Constraint_programming ），然后调用求解器解决。推荐 google ortools ( https://developers.google.com/optimization)
2. 近似解法 -- 如果不想特别研究问题结构，可以上元启发方法（ https://en.wikipedia.org/wiki/Metaheuristic ），例如遗传算法、淬火、领域搜索等。搞法是把解编码成这些算法的一个数据结构，然后嵌入主逻辑然后求解。
第二种就是利用问题结构，自己发明一个启发式解法，例如贪心算法等。但是 LZ 你这个问题是个约束满足问题（ SAT ），启发式算法开发不太好弄，因为没有很明显的问题结构可以利用。

希望有所帮助

[montaro2017]

一看好像是动态规划啊，不过我算法学的不好

[A3]

面试题有了

[ElmerZhang]

总结一下楼上的回复：会的懒得写，不会的写不出来。
我属于不会的。

[iOCZ]

从一堆数里分成若干堆，你可以很容易计算出每一堆的总和，但你很难反推出每一堆是哪几个数，NP hard 。

[Zakl21]

感觉可以写个暴搜解，但是数据量大的情况下，耗时有点不太好看

[xz410236056]

你这个问题 本质上实在寻找和为定值的多个数，leetcode 是有这个题的，叫 N-sum 。网上很多解法，我抄几个来。
https://zhuanlan.zhihu.com/p/45229612
https://www.jianshu.com/p/3d1791cfba53
https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/02.03.html

[EugeneYWang]

@A3 做个人吧，出这种程度的 DP 。要不是不想招人就是只想面人摸鱼是吧

[diandian666]

@maggch97 大佬牛啤啊。您这个是秒出结果啊。我再找找几组数据看看

[lzyliangzheyu]

@xz410236056 你好，请问你发的这个第三个 URL ，只能看这个页面吗，我看大纲里有好多内容，但是点了别的就报 401

[lzyliangzheyu]

@xz410236056 解决了，登陆一下就能看了。。。。。。。。。

[shyrock]

OP 要不介绍一下这个算法解决的实际问题是什么？

刷过算法题一大堆，这还是第一次看到在实际应用中需要解高难度算法题的

[Immortan]

很多解法，不过我最喜欢的还是 A*搜索，简单粗暴有效。

[Damn]

@maggch97
@diandian666 楼主看一下 74 楼，这是一个非常古老的问题，多年之前在论坛上作为挑战题目比赛过。。。

[xinxiaotain]

觉得 在数据源头解决 比找到一个算法解决这个问题 更容易

[diandian666]

@maggch97 新尝试了其他 3 组其他数据，两组正常出结果，有一组没出结果。很不错了。以下贴出未出结果的数据

数组 1：
[1.52,1.68,0.96,8.40,9.08,11.40]

数组 2：
[1.40,0.28,0.28,0.28,0.84,0.56,0.56,0.84,0.28,0.28,0.40,0.28,0.28,0.84,0.28,0.28,0.28,0.56,0.84,0.28,0.56,0.28,0.80,0.80,0.80,0.28,0.28,0.28,0.28,0.28,0.28,1.40,0.28,0.28,0.56,0.28,3.36,0.56,0.28,0.84,0.84,1.68,3.36,1.68,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28,0.28]

[diandian666]

@Damn 我去学习学习，哈哈

[diandian666]

@Damn 好的。我去看看。