这是一个创建于 748 天前的主题，其中的信息可能已经有所发展或是发生改变。
如题，各位大佬摸鱼的时间看看怎么解决！！感谢！ 感恩！思密达！
公司业务需要，把我难倒了。各位大佬看看能不能摸鱼的时间来看看这个需求。代码递归跑的内存都溢出了，万分感谢。
题目：
有两组数字数组数据，数组 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
]
 |
101
ajaxgoldfish 2022-11-15 20:53:17 +08:00
我也不会，大家觉得和”田忌赛马“的剪枝法那个思路沾边吗
|
|
102
ajaxgoldfish 2022-11-15 20:58:26 +08:00
楼主是暴力递归吗，可以加一些判断条件，先算出来 1 组中第一项对应的数据，假如 1 组中的第一项数据对应的第二组数据只有一种情况可以直接 ruturn ，意思就是分治法一次别算到底分组算，分步+分组。
|
|
103
ajaxgoldfish 2022-11-15 20:58:58 +08:00
@ajaxgoldfish return
|
|
104
ajaxgoldfish 2022-11-15 21:07:25 +08:00
既然人工对出来这种方法也能跑出来，这就是人工的那个思路，先算 1 组中第一个数据对应的集合。然后再算第二组的。第一组如果有多种可能的话那就再跑第二组。前提是跑第一组的数据和第二组是一样的，不用剔除第一组选中的数据，剔除就麻烦了，就涉及到回溯法了。这样分组跑后边再判断
|
|
105
ajaxgoldfish 2022-11-15 21:10:37 +08:00
这样程序第一步时间复杂度就直接是 n 。。。。搬个板凳听下面大佬的更好的方法。最近也有类似需求
|
 |
106
jimliang 2022-11-15 21:36:03 +08:00
背包问题的变种。
|
 |
107
maggch97 2022-11-15 21:48:20 +08:00
我错了，这个数据量随机的话减枝搜+DP 复杂度也是爆炸的
我要吐槽一下，你给的第一组数据是错的。数组 1 的和和数组 2 的和差了 0.01 上面有人给出了 python 代码，直接数组 2 里面每次取最大的去凑数组 1 里面最小的数字。我怀疑你们的数据全都是这个策略就能有解的。 |
 |
111
timjuly 2022-11-15 22:27:23 +08:00
这两组数据都是有根据出来的，绝对能匹配成功
------ 既然有根据，为啥不让上游出数据的时候给你分好组，上游比你有更多的办法解。 |
 |
112
2NUT 2022-11-15 22:49:01 +08:00
显然你的抽象没有利用足够的业务信息
|
|
114
maggch97 2022-11-15 23:36:24 +08:00  2
@wxf666 https://maggch97.github.io/dfs/dfs.html 你要跑的话可以试试我这个 js 写的，至少楼主给的几个数据都能出结果
|
 |
115
iOCZ 2022-11-15 23:38:46 +08:00
这是一个组合问题，但是没有明显能快速收敛的条件。
|
 |
116
mochen666 2022-11-15 23:43:23 +08:00 1
题主，小弟刚才人工算了一下，你看结果是不是比你给的运算量小。
我的思路是从数组 1 中最小得数 a 开始，用数组 2 中比 a 小得数从前往后开始求和 17.76>=5.88+5.04+3.64+2.8 26.67>=3.45+3.36+2.8+2.52+2.24 62.13>=数组 2 剩下得那一串串 能否给你点启发 |
 |
117
TongNianShanHe 2022-11-15 23:48:54 +08:00 1
楼上的大佬们也说过了这是 NP 问题，直接用动态规划或者剪枝啥的。。。数据量小可以，数据量大除非你租个天河（
我这边斗胆开个脑洞：不死钻这两组数据，既然这组数据是一组实际的下单和退单数据，那么肯定有时间吧，根据时间进行排序，然后再用 KMP 或者滑动窗口试试？（不一定对，如有误还请指正） |
 |
118
Xs0ul 2022-11-16 01:05:22 +08:00
1. 虽然大佬提了这是 NP 问题，如果两组数据全随机复杂度爆炸。但从楼主给的例子来看，数组 2 显然有很多小的而且重复的数字，转化成(value, count)能让暴力搜索的复杂度减少很多
2. 实践上来说，或许可以考虑设置一个 timeout ，1 分钟没搜出来就交给人工 |
 |
119
nuk 2022-11-16 03:03:18 +08:00
是算财务的吧？以前写过类似的，就是背包问题，数据量多的话基本没法求解，只能循环遍历，财务经常抱怨程序运行了一天一夜也跑完。
|
 |
120
crab 2022-11-16 03:55:34 +08:00
LeetCode 组合总和 可以看看。
之前转运合并包裹重量用这个算的。 |
 |
121
superhxl 2022-11-16 04:30:51 +08:00 via Android
楼主数组 2 数据看似挺多，但实际上有很多重复的，所以先统计出数据项及个数。然后采用数学规划的方法，建立一个整数规划模型，直接调用开源求解器求解肯定比自己写算法快！个人看法
|
 |
123
dayeye2006199 2022-11-16 08:37:58 +08:00 12
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 ），启发式算法开发不太好弄，因为没有很明显的问题结构可以利用。 希望有所帮助 |
 |
124
montaro2017 2022-11-16 08:43:34 +08:00
一看好像是动态规划啊，不过我算法学的不好
|
 |
125
A3 2022-11-16 08:43:51 +08:00 via Android
面试题有了
|
 |
126
ElmerZhang 2022-11-16 08:57:00 +08:00 via iPhone 1
总结一下楼上的回复：会的懒得写，不会的写不出来。
我属于不会的。 |
|
127
iOCZ 2022-11-16 09:09:21 +08:00
从一堆数里分成若干堆，你可以很容易计算出每一堆的总和，但你很难反推出每一堆是哪几个数，NP hard 。
|
 |
128
Zakl21 2022-11-16 09:09:58 +08:00
感觉可以写个暴搜解，但是数据量大的情况下，耗时有点不太好看
|
 |
129
xz410236056 2022-11-16 09:26:32 +08:00
你这个问题 本质上实在寻找和为定值的多个数，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 |
 |
130
EugeneYWang 2022-11-16 09:37:43 +08:00
@A3 做个人吧，出这种程度的 DP 。要不是不想招人就是只想面人摸鱼是吧
|
 |
131
diandian666 OP @maggch97 大佬牛啤啊。您这个是秒出结果啊。我再找找几组数据看看
|
 |
132
lzyliangzheyu 2022-11-16 10:08:13 +08:00
@xz410236056 你好，请问你发的这个第三个 URL ，只能看这个页面吗，我看大纲里有好多内容，但是点了别的就报 401
|
|
133
lzyliangzheyu 2022-11-16 10:09:29 +08:00
@xz410236056 解决了，登陆一下就能看了。。。。。。。。。
|
 |
134
shyrock 2022-11-16 10:24:47 +08:00
OP 要不介绍一下这个算法解决的实际问题是什么？
刷过算法题一大堆，这还是第一次看到在实际应用中需要解高难度算法题的 |
 |
135
Immortan 2022-11-16 10:41:08 +08:00
很多解法，不过我最喜欢的还是 A*搜索，简单粗暴有效。
|
 |
136
Damn 2022-11-16 10:59:45 +08:00 via iPhone
|
 |
137
xinxiaotain 2022-11-16 11:01:58 +08:00
觉得 在数据源头解决 比找到一个算法解决这个问题 更容易
|
|
138
diandian666 OP @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] |
|
139
diandian666 OP @Damn 我去学习学习，哈哈
|
|
140
diandian666 OP @Damn 好的。我去看看。
|
|
142
diandian666 OP @maggch97
前面回复的那组不成功的数据。因为数据有其他同类型元素可以合并起来，我这边可以合并的数据数据是下面，合并后的能成功出结果。 数组 1： [21.04,15.08,2.52] 数组 2: [3.36,3.36,2.52,1.68,1.68,1.40,1.40,1.40,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.80,0.80,0.80,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.40,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,0.28,0.28,0.28] |
|
143
maggch97 2022-11-16 11:33:11 +08:00
@Damn 我知道 NP ，但是如果人手都能凑出来说明数据保证了凑出解的概率非常大。凑数字这种人脑根本没优势的项目，机器不可能比人差。
@diandian666 我代码确实还有些问题，sort 都是错的，还有重复搜索的问题。但是回到你这个问题，你这组数据凑不出解的。只有一个 0.4 但是 1.52 和 0.96 凑出来都需要 0.4 0.96 = 0.4+0.28*2 1.54 = 0.28*4+0.4 只有上面一种凑法 |
 |
144
maplelin 2022-11-16 11:39:43 +08:00
感觉这种具体业务的数据，如果有些其他关联性的结论用来剪枝就好了，毕竟人工可以得出解，算法的话应该有技巧可以优化的。
|
|
145
diandian666 OP @maggch97 这组数据其实还有其他数据的。只是我在两个数组中，去掉两个数组都一样的值剩下的。估计我的数据确实是需要把相同属性的合并起来在匹配。后面已经贴出来没有去除两个数组相同的值且把数组 1 相同属性的合并起来后，再用你的代码匹配。确实成功了。真不错。666 啊
|
|
146
maggch97 2022-11-16 11:50:25 +08:00
@diandian666 去掉相同的这个优化没有问题，问题是你的 1 数据不合并可能根本凑不出解
|
|
147
Damn 2022-11-16 11:52:33 +08:00 1
|
|
148
diandian666 OP @maggch97 我这边也顺便贴出来没有合并数组 1 前的数据数据。看大佬有没有兴趣研究，不排除我的数据是一定需要合并才能匹配，因为原题那三组数据的数组 1 确实是我合并后的，因为合并数组 1 后，能匹配出来。也能解决问题了。
数组 1： [2.52,11.4,0.56,9.08,8.4,1.4,0.84,0.96,1.68,1.52,0.28] 数组 2： [3.36,3.36,2.52,1.68,1.68,1.40,1.40,1.40,0.84,0.84,0.84,0.84,0.84,0.84,0.84,0.80,0.80,0.80,0.56,0.56,0.56,0.56,0.56,0.56,0.56,0.40,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,0.28,0.28,0.28] |
|
149
diandian666 OP @maggch97 哈哈，对的。我现在也怀疑这个，因为原题给的几组都是合并数组 1 的。
|
|
150
maggch97 2022-11-16 11:56:45 +08:00 via Android
@diandian666 我上面说了，你 2 数组里只有一个 0.4 是凑不出 1 数组里的 0.96 和 1.52 的。你手算试试用 2 数组里面的数字去凑凑看，能不能凑出这两个数字
|
|
151
A3 2022-11-16 12:01:01 +08:00 via Android
@EugeneYWang 我不是面试官🙈
|
 |
152
haichaofine32 2022-11-16 12:16:31 +08:00 via Android
好奇，这题能否反过来做？也就是给定一个数组，取任意个数值相加，看能得出多少不同的结果？猜测循环次数应该是折半的，例如九个数任取两个不重复，和九个数任取 7 个不重复是一个种状态。非专业，大佬忽喷
|
|
153
diandian666 OP @maggch97 似乎还真是。大佬 666 ，
|
 |
154
Innovatino 2022-11-16 12:38:00 +08:00 via iPhone
@diandian666 建议买杯咖啡给大佬🤣
|
 |
155
sdushn 2022-11-16 14:01:51 +08:00
回溯？
|
 |
156
14104chk 2022-11-16 14:22:44 +08:00
|
 |
157
bosskwei 2022-11-16 14:41:39 +08:00
你这个问题很简单，实际上可以认为是一个近似矩阵乘法的操作。矩阵的 element 只有 0 或 1
|
 |
158
lyminghao 2022-11-16 15:01:04 +08:00
相当于迭代地求解 subset sum 问题（ 0-1 背包的一个变体），是 NP 完全的。
当然自己写个搜索算法也 ok ，但是像这种难度的问题，还是建议试下用求解器解决。比如建模成一个 0-1 整数规划问题，送进 CPLEX ，Gurobi 直接就有答案了。 如果人肉眼都能配出解来，那对这些求解器肯定是能秒出结果的。 |
|
159
lyminghao 2022-11-16 15:09:00 +08:00
@optional 很简单啊，设数组一为 A ，数组二为 B ；布尔变量 x[i,j]表示 B[j]匹配到 A[i]；
约束： forall (i in 1...|A|) (sum (j in 1...|B|) (x[i,j] * B[j]) == A[i]); // 满足求和要求 forall (j in 1...|B|) (sum (i in 1...|A|) (x[i,j]) == 1); // B 到 A 匹配唯一 |
 |
160
mylove614 2022-11-16 15:15:49 +08:00
建议发在 icpc 或者 oi 的群里，大佬应该会给你答案的
|
 |
161
Nazz 2022-11-16 15:32:28 +08:00
以测试数据为例, 使用 dp 算法求出 3 组数据, 然后三层循环找出一个没有交集的组合
|
 |
162
SenseHu 2022-11-16 15:40:25 +08:00
@diandian666 "不知道呢，一组数据是付款订单。另一组数据是移除订单。反正就是这两个不互通。需要自己匹配关联呢。"
so 付款订单其实是由若干商品组合成，移除的时候可能单独移除了一两个，那付款订单其实把商品 id 带上的话，这个问题会简化很多？ |
|
164
diandian666 OP @SenseHu 两组数据的订单号全部是一样的呢。只是一组有地区，另一组没地区。需要匹配成功后，也把地区填充到另一组。
|
 |
165
binxin 2022-11-16 16:34:09 +08:00
OP 主楼里面的两个 case 都解出来了，正要过来 show 一下，发现 op re 的那个长 case 报“maximum recursion depth exceeded”了。
|
 |
166
gold2022 2022-11-16 16:38:09 +08:00
|
 |
167
nielinjie 2022-11-16 17:26:18 +08:00
不是应该先采访下人工队是怎么做的么？
|
 |
168
Keen06 2022-11-16 17:46:22 +08:00
我写了一个暴力解法,时间复杂度 O(n^m), n 、m 分别表示数组 1 和数组 2 的元素个数, 空间复杂度 O(m)。
两个简单例子可以跑通, 第一个例子时间复杂度约为 3.99084e+39 ，显然超时了。。。 代码如下：本来想发 gist 链接，但网站提示我像在 spamming ''' #include<iostream> #include<vector> #include<list> #include<cmath> using namespace std; void helper(vector<double>& arr1,int n, vector<double>& arr2, int start, int m, vector<list<double>>& res,bool& isok){ //暴力法:将 arr2 中的 m 个数分成 n 堆,编号 0~n-1 堆,堆 i 中数的和等于 arr1[i] //对于 arr2 中的每个数有 n 中选择,放入哪个堆中,穷举加回溯 //时间复杂度为 O(n^m),空间复杂度为解空间树的深度 O(m) if(isok) return; //isok 表示是否找到解 if(start==m) {//因为两个数组总的和相等,并且在递归过程中 arr1 数组中个数都不会<0,所以如果遍历到最后说明 arr2 中所有数都放在正确的堆中 isok = true; return; } for(int i=0;i<n;++i){ if(arr1[i]>arr2[start]||fabs(arr1[i]-arr2[start])<0.00001){//arr1[i]>=arr2[start]时可以放入 arr2[start] res[i].push_back(arr2[start]); arr1[i] -= arr2[start]; helper(arr1,n,arr2,start+1,m,res,isok);//递归查找解 arr1[i] += arr2[start];//回溯 if(!isok) res[i].pop_back();//若未找到解则回溯 else return;//找到则直接返回 } } } int main(){ // vector<double> arr1 = {62.13,26.67,17.76}; // vector<double> arr2 = {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}; //采用这组数据时,n=3,m=83,时间复杂度为 O(n^m)3.99084e+39 // vector<double> arr1 = {52.7,8.96}; // vector<double> arr2 = {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}; vector<double> arr1 = {23.17,3.2,1.22,0.32}; vector<double> arr2 = {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}; int n = arr1.size(); int m = arr2.size(); cout<<"len of arr1 is "<<n<<endl; cout<<"len of arr2 is "<<m<<endl; cout<<"n^m is "<<pow(n,m)<<endl; vector<list<double>> res(n); bool isok = false; helper(arr1,n,arr2,0,arr2.size(),res,isok); for(int i=0;i<n;++i){ cout<<arr1[i]<<":\n"; double sum = 0; for(double j:res[i]){ cout<<j<<' '; sum += j; } cout<<'\n'; bool correct = fabs(sum-arr1[i])<0.000001?true:false;//验证解法是否正确 cout<<"sum is "<<sum<<", "; cout<<"the result is "<<(correct?"correct":"wrong")<<'\n'; } return 0; } ''' |
 |
169
brader 2022-11-16 18:32:11 +08:00
我建议直接暴力穷举，因为既然人工能看的过来，不可能计算机穷举不完
|
 |
170
cnuser002 2022-11-16 20:33:35 +08:00
额，楼主，我有个思路，不知道能不能帮到你啊。
我观察了一下你这个数据的构成。有很多形如 0.28,0.56 这种小数字。这些小数字拉高了遍历的轮次，导致你算不出来。 可不可以把这一大坨小数字，合成几个大数字，再参与你的遍历。出了结果后，再把它分解回小数字呢？ 以你主题中的例子， 有 30 个 0.28 ， 要匹配 3 个数。 一个数字中的 0.28 的数量,可以表示为 2n 或者 2n+1 。 这里 2n 个 0.28 ，可以转成 n 个 0.56 。 根据鸽笼原理，3 个数，我们留 3 个 0.28 参与最后的匹配，剩下的 27 个 0.28 ，都换成 0.56 。 同样的，2n 个 0.56 可以换成 n 个 1.12... 这样参与最终匹配的数字降下来，你这个问题就能找出解。 找出解以后，你再还原回去。 |
 |
172
zengguibo 2022-11-16 21:50:45 +08:00
我觉得你可能漏了一些业务信息，这些数字靠人工很难凑出来的
|
 |
173
Building 2022-11-16 21:59:44 +08:00
第一步：
在 a0 - an 个 数中：(A + B + C) = (a0 + ...+ a100) 得到子集合 (an + ... + am) ... (an1 + ... am1) 第二步约束： (A + B) = (an + ... + am) && C = an1 + ... + am1 (A + C) = (an + ... + am) && B = an1 + ... + am1 (B + C) = (an + ... + am) && A = an1 + ... + am1 |
 |
174
mmdsun 2022-11-16 22:25:07 +08:00
|
 |
175
quxw 2022-11-17 00:21:29 +08:00 1
写了一个,三个都能很快跑出来,是穷举优化了下.
https://gist.github.com/quxiaowei/ccb676bf2b66a4b0f9a35b959e0e7d09 |
 |
176
hicdn 2022-11-17 02:47:48 +08:00 1
@quxw 的版本能行，就是算的太慢，风扇起飞。
加上 cache 后，秒出结果。给递归加 cache ，常见的优化策略。 https://gist.github.com/4ft35t/814b5ba8bba6cf1a2fc3dc14db818cb9 |
|
177
superhxl 2022-11-17 07:13:54 +08:00 via Android
@optional 数组 1 用 i 索引，数组 2 用 j 索引，xij 为整数变量，表示数组 1 元素的加和中用到了 xij 个数组 2 的 j 元素！约束条件为数组 2 元素数量约束，即数组 2 中的元素数量限制！目标函数你可以用数组 1 的表示值和真实值误差最小
|
 |
178
optional 2022-11-17 07:16:19 +08:00 via iPhone
@superhxl 我看的懂你的模型，不用解释，关键是这个模型本质上就是暴搜，数量稍微大点，出不来的。
|
 |
180
zjsxwc 2022-11-17 08:47:31 +08:00
因为没有唯一解（最优解）所以不大会考虑直接用动态规划思路，
于是考虑暴力搜索 dfs 、bfs 加 剪支。 |
 |
181
StrayBugs 2022-11-17 08:52:58 +08:00 via Android
凑硬币，先倒序排序，然后先凑大后凑小地 dfs 。
|
 |
182
acerphoenix 2022-11-17 09:08:10 +08:00 1
你这问题很难啊，解不是唯一的，而且还得考虑一个和数能用到这里，也能用到那里，但实际只能用到那里，但你先用到这里导致最后算不出来。
|
 |
184
xuelu520 2022-11-17 09:54:24 +08:00
我第一想到是暴力递归，不过感觉还是有点难搞
|
 |
185
PinkLadyMage 2022-11-17 10:22:19 +08:00
这是资金盘 /互助系统的逻辑吗
|
 |
186
mystrylw 2022-11-17 11:21:54 +08:00
这问题我一直用 excel 的规划求解做 数据量少一点还能跑 数据量大了 单线程跑半天
|
 |
187
xuxuzhaozhao 2022-11-17 11:29:24 +08:00 1
我喜欢这种问题，看完脑子有点痒，感觉要长脑子了。
|
|
188
diandian666 OP @quxw 晚点，我测试下，这会有点忙，也没能及时回复大伙。
|
|
189
diandian666 OP 好多回复都没能及时。感谢各位热心回复的人儿啊。特别是那些提供建议或者代码的，棒棒的。晚点有空的时候，我在细溜各位的留言...再次感谢..
|
 |
190
dallaslu 2022-11-17 12:48:56 +08:00
|
|
191
dallaslu 2022-11-17 13:07:30 +08:00
@dallaslu 以小凑小有陷阱，以大凑大也有陷阱：1+14+15 = 1+4+11+14 ，若先算出 15=14 + 1 ，后续也失败了。以大凑小也一样，21+26+50=1+10+11+20+25+30 ，先算出 21 = 20+1 ，同样失败
|
|
192
superhxl 2022-11-17 13:14:49 +08:00 via Android
@optional 爆搜不至于吧！前面很多人提的分枝、剪枝、深广度搜素实际都已经集成到求解器中，个人感觉肯定比自己搜要快！
|
 |
194
zer0fire 2022-11-17 14:03:20 +08:00
说下思路, 以第一组数据为例:
1. 简化数据集, 找出最大公约数,且数组 1 正序排序, 数组 2 逆序 数组 1: [52.7,8.96]->[5270,896]->2[448, 2635] 数组 2: [21.44,...0.32]->[2144,...32]->2[1072...16] 2. 从数组 1 最小的开始尽可能找出包含数组 2 大数的集合(理由数组 1 的大数可以由多个数组 2 的小数合成) 数组 1 的 448[index=0] == 数组 2 的 448[index=4] 数组 2 的 2635[index=1]==数组 2 的 1072[index=1]+...+16[index=lenght-1] 3. 由此可以得到结果 |
|
195
zer0fire 2022-11-17 14:17:40 +08:00
@zer0fire 为解决数组 2 的最大公约数不等同与数组 1 的最大公约数, 可以先对数组 2 做逆序, 让最大的元素与其他的元素组合在一次成为最接近它的数组 1 的公倍数
|
|
196
maggch97 2022-11-17 15:28:32 +08:00
不要期望找一个策略就能完全解决这个问题，要是真有 NP=P 就成立了。只有暴搜一条路，可以加暴搜+剪枝，暴搜+DP 稍微优化一下，不过这些优化对原问题都是杯水车薪。
最终让上面所有代码跑起来的前提是，楼主的数据是人手都能凑出来的数据，说明了搜索空间里面解的占比非常大。 |
 |
197
bluefountain 2022-11-17 15:34:53 +08:00
excel 的第三方插件能干这个
|
 |
198
bugmaker233 2022-11-17 17:34:23 +08:00
@xuxuzhaozhao 哈哈和我一样
|
 |
199
forty 2022-11-17 17:55:29 +08:00
生成 1 个接近的结果给人工去调整应该也能大大节省人工
|
Select Language