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

2022 年 11 月 15 日
 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

]

28488 次点击
所在节点    程序员
207 条回复
StrayBugs
2022 年 11 月 17 日
凑硬币,先倒序排序,然后先凑大后凑小地 dfs 。
acerphoenix
2022 年 11 月 17 日
你这问题很难啊,解不是唯一的,而且还得考虑一个和数能用到这里,也能用到那里,但实际只能用到那里,但你先用到这里导致最后算不出来。
weeei
2022 年 11 月 17 日
@dallaslu 不像是凑发票,还记得以前的 P2P 理财产品是怎么分配用户的资金吗?这个算法很 P2P 很像。
xuelu520
2022 年 11 月 17 日
我第一想到是暴力递归,不过感觉还是有点难搞
PinkLadyMage
2022 年 11 月 17 日
这是资金盘 /互助系统的逻辑吗
mystrylw
2022 年 11 月 17 日
这问题我一直用 excel 的规划求解做 数据量少一点还能跑 数据量大了 单线程跑半天
xuxuzhaozhao
2022 年 11 月 17 日
我喜欢这种问题,看完脑子有点痒,感觉要长脑子了。
diandian666
2022 年 11 月 17 日
@quxw 晚点,我测试下,这会有点忙,也没能及时回复大伙。
diandian666
2022 年 11 月 17 日
好多回复都没能及时。感谢各位热心回复的人儿啊。特别是那些提供建议或者代码的,棒棒的。晚点有空的时候,我在细溜各位的留言...再次感谢..
dallaslu
2022 年 11 月 17 日
@quxw
@hicdn
有时会有陷阱的。比如 20+21+26 = 10+10+11+15+20 ,若先算出 20=10+10……
dallaslu
2022 年 11 月 17 日
@dallaslu 以小凑小有陷阱,以大凑大也有陷阱:1+14+15 = 1+4+11+14 ,若先算出 15=14 + 1 ,后续也失败了。以大凑小也一样,21+26+50=1+10+11+20+25+30 ,先算出 21 = 20+1 ,同样失败
superhxl
2022 年 11 月 17 日
@optional 爆搜不至于吧!前面很多人提的分枝、剪枝、深广度搜素实际都已经集成到求解器中,个人感觉肯定比自己搜要快!
optional
2022 年 11 月 17 日
@superhxl 你的约束模型得有剪枝空间才行,比如一个 LP 条件
zer0fire
2022 年 11 月 17 日
说下思路, 以第一组数据为例:
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. 由此可以得到结果
zer0fire
2022 年 11 月 17 日
@zer0fire 为解决数组 2 的最大公约数不等同与数组 1 的最大公约数, 可以先对数组 2 做逆序, 让最大的元素与其他的元素组合在一次成为最接近它的数组 1 的公倍数
penzi
2022 年 11 月 17 日
不要期望找一个策略就能完全解决这个问题,要是真有 NP=P 就成立了。只有暴搜一条路,可以加暴搜+剪枝,暴搜+DP 稍微优化一下,不过这些优化对原问题都是杯水车薪。

最终让上面所有代码跑起来的前提是,楼主的数据是人手都能凑出来的数据,说明了搜索空间里面解的占比非常大。
bluefountain
2022 年 11 月 17 日
excel 的第三方插件能干这个
bugmaker233
2022 年 11 月 17 日
@xuxuzhaozhao 哈哈和我一样
forty
2022 年 11 月 17 日
生成 1 个接近的结果给人工去调整应该也能大大节省人工
yuruizhe
2022 年 11 月 17 日
@wfd0807 同+1
dp[i][j]表示 a[0]~a[i]求和构成 j 的方案总数
dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]]
为每一个 j 求出候选集
然后二分图,求完美匹配

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://v2ex.ih06.com/t/895464

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX