V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
diandian666
V2EX  ›  程序员

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

  •  
  •   diandian666 · 2022-11-15 17:40:20 +08:00 · 23834 次点击
    这是一个创建于 499 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如题,各位大佬摸鱼的时间看看怎么解决!!感谢! 感恩!思密达!

    公司业务需要,把我难倒了。各位大佬看看能不能摸鱼的时间来看看这个需求。代码递归跑的内存都溢出了,万分感谢。

    题目:

    有两组数字数组数据,数组 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

    ]

    207 条回复    2022-12-29 16:28:29 +08:00
    1  2  3  
    ajaxgoldfish
        101
    ajaxgoldfish  
       2022-11-15 20:53:17 +08:00
    我也不会,大家觉得和”田忌赛马“的剪枝法那个思路沾边吗
    ajaxgoldfish
        102
    ajaxgoldfish  
       2022-11-15 20:58:26 +08:00
    楼主是暴力递归吗,可以加一些判断条件,先算出来 1 组中第一项对应的数据,假如 1 组中的第一项数据对应的第二组数据只有一种情况可以直接 ruturn ,意思就是分治法一次别算到底分组算,分步+分组。
    ajaxgoldfish
        103
    ajaxgoldfish  
       2022-11-15 20:58:58 +08:00
    @ajaxgoldfish return
    ajaxgoldfish
        104
    ajaxgoldfish  
       2022-11-15 21:07:25 +08:00
    既然人工对出来这种方法也能跑出来,这就是人工的那个思路,先算 1 组中第一个数据对应的集合。然后再算第二组的。第一组如果有多种可能的话那就再跑第二组。前提是跑第一组的数据和第二组是一样的,不用剔除第一组选中的数据,剔除就麻烦了,就涉及到回溯法了。这样分组跑后边再判断
    ajaxgoldfish
        105
    ajaxgoldfish  
       2022-11-15 21:10:37 +08:00
    这样程序第一步时间复杂度就直接是 n 。。。。搬个板凳听下面大佬的更好的方法。最近也有类似需求
    jimliang
        106
    jimliang  
       2022-11-15 21:36:03 +08:00
    背包问题的变种。
    maggch97
        107
    maggch97  
       2022-11-15 21:48:20 +08:00
    我错了,这个数据量随机的话减枝搜+DP 复杂度也是爆炸的

    我要吐槽一下,你给的第一组数据是错的。数组 1 的和和数组 2 的和差了 0.01

    上面有人给出了 python 代码,直接数组 2 里面每次取最大的去凑数组 1 里面最小的数字。我怀疑你们的数据全都是这个策略就能有解的。
    maggch97
        108
    maggch97  
       2022-11-15 21:50:21 +08:00
    @maggch97 我写了一堆代码,发现结果全都是按照上面的策略就有解,你不妨多贴一点数据出来验证一下
    maggch97
        109
    maggch97  
       2022-11-15 21:58:26 +08:00
    @maggch97 看错了,数据没有错。我取*100 取 int 的时候被被舍掉了 1
    maggch97
        110
    maggch97  
       2022-11-15 22:04:27 +08:00
    @wxf666 int(1.15*100) == 1.14
    timjuly
        111
    timjuly  
       2022-11-15 22:27:23 +08:00
    这两组数据都是有根据出来的,绝对能匹配成功
    ------
    既然有根据,为啥不让上游出数据的时候给你分好组,上游比你有更多的办法解。
    2NUT
        112
    2NUT  
       2022-11-15 22:49:01 +08:00
    显然你的抽象没有利用足够的业务信息
    wxf666
        113
    wxf666  
       2022-11-15 22:52:20 +08:00
    @maggch97 确实,改成 round(1.15 * 100) 就能继续跑了

    但跑了快半个钟了,还没出结果。。
    maggch97
        114
    maggch97  
       2022-11-15 23:36:24 +08:00   ❤️ 2
    @wxf666 https://maggch97.github.io/dfs/dfs.html 你要跑的话可以试试我这个 js 写的,至少楼主给的几个数据都能出结果
    iOCZ
        115
    iOCZ  
       2022-11-15 23:38:46 +08:00
    这是一个组合问题,但是没有明显能快速收敛的条件。
    mochen666
        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 剩下得那一串串
    能否给你点启发
    TongNianShanHe
        117
    TongNianShanHe  
       2022-11-15 23:48:54 +08:00   ❤️ 1
    楼上的大佬们也说过了这是 NP 问题,直接用动态规划或者剪枝啥的。。。数据量小可以,数据量大除非你租个天河(
    我这边斗胆开个脑洞:不死钻这两组数据,既然这组数据是一组实际的下单和退单数据,那么肯定有时间吧,根据时间进行排序,然后再用 KMP 或者滑动窗口试试?(不一定对,如有误还请指正)
    Xs0ul
        118
    Xs0ul  
       2022-11-16 01:05:22 +08:00
    1. 虽然大佬提了这是 NP 问题,如果两组数据全随机复杂度爆炸。但从楼主给的例子来看,数组 2 显然有很多小的而且重复的数字,转化成(value, count)能让暴力搜索的复杂度减少很多
    2. 实践上来说,或许可以考虑设置一个 timeout ,1 分钟没搜出来就交给人工
    nuk
        119
    nuk  
       2022-11-16 03:03:18 +08:00
    是算财务的吧?以前写过类似的,就是背包问题,数据量多的话基本没法求解,只能循环遍历,财务经常抱怨程序运行了一天一夜也跑完。
    crab
        120
    crab  
       2022-11-16 03:55:34 +08:00
    LeetCode 组合总和 可以看看。
    之前转运合并包裹重量用这个算的。
    superhxl
        121
    superhxl  
       2022-11-16 04:30:51 +08:00 via Android
    楼主数组 2 数据看似挺多,但实际上有很多重复的,所以先统计出数据项及个数。然后采用数学规划的方法,建立一个整数规划模型,直接调用开源求解器求解肯定比自己写算法快!个人看法
    optional
        122
    optional  
       2022-11-16 07:52:55 +08:00 via iPhone
    @superhxl 呵呵,整数规划,你倒是说说这个约束怎么写
    dayeye2006199
        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 ),启发式算法开发不太好弄,因为没有很明显的问题结构可以利用。

    希望有所帮助
    montaro2017
        124
    montaro2017  
       2022-11-16 08:43:34 +08:00
    一看好像是动态规划啊,不过我算法学的不好
    A3
        125
    A3  
       2022-11-16 08:43:51 +08:00 via Android
    面试题有了
    ElmerZhang
        126
    ElmerZhang  
       2022-11-16 08:57:00 +08:00 via iPhone   ❤️ 1
    总结一下楼上的回复:会的懒得写,不会的写不出来。
    我属于不会的。
    iOCZ
        127
    iOCZ  
       2022-11-16 09:09:21 +08:00
    从一堆数里分成若干堆,你可以很容易计算出每一堆的总和,但你很难反推出每一堆是哪几个数,NP hard 。
    Zakl21
        128
    Zakl21  
       2022-11-16 09:09:58 +08:00
    感觉可以写个暴搜解,但是数据量大的情况下,耗时有点不太好看
    xz410236056
        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
    EugeneYWang
        130
    EugeneYWang  
       2022-11-16 09:37:43 +08:00
    @A3 做个人吧,出这种程度的 DP 。要不是不想招人就是只想面人摸鱼是吧
    diandian666
        131
    diandian666  
    OP
       2022-11-16 09:51:26 +08:00
    @maggch97 大佬牛啤啊。您这个是秒出结果啊。我再找找几组数据看看
    lzyliangzheyu
        132
    lzyliangzheyu  
       2022-11-16 10:08:13 +08:00
    @xz410236056 你好,请问你发的这个第三个 URL ,只能看这个页面吗,我看大纲里有好多内容,但是点了别的就报 401
    lzyliangzheyu
        133
    lzyliangzheyu  
       2022-11-16 10:09:29 +08:00
    @xz410236056 解决了,登陆一下就能看了。。。。。。。。。
    shyrock
        134
    shyrock  
       2022-11-16 10:24:47 +08:00
    OP 要不介绍一下这个算法解决的实际问题是什么?

    刷过算法题一大堆,这还是第一次看到在实际应用中需要解高难度算法题的
    Immortan
        135
    Immortan  
       2022-11-16 10:41:08 +08:00
    很多解法,不过我最喜欢的还是 A*搜索,简单粗暴有效。
    Damn
        136
    Damn  
       2022-11-16 10:59:45 +08:00 via iPhone
    @maggch97
    @diandian666 楼主看一下 74 楼,这是一个非常古老的问题,多年之前在论坛上作为挑战题目比赛过。。。
    xinxiaotain
        137
    xinxiaotain  
       2022-11-16 11:01:58 +08:00
    觉得 在数据源头解决 比找到一个算法解决这个问题 更容易
    diandian666
        138
    diandian666  
    OP
       2022-11-16 11:08:07 +08:00
    @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
        139
    diandian666  
    OP
       2022-11-16 11:10:41 +08:00
    @Damn 我去学习学习,哈哈
    diandian666
        140
    diandian666  
    OP
       2022-11-16 11:11:11 +08:00
    @Damn 好的。我去看看。
    SimonOne
        141
    SimonOne  
       2022-11-16 11:24:12 +08:00
    @Damn #136 兄弟能具体说下是哪条回复吗,因为每个人的 block 名单都不一样,所以楼层数大家应该都不一样的
    diandian666
        142
    diandian666  
    OP
       2022-11-16 11:29:52 +08:00
    @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]
    maggch97
        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
    只有上面一种凑法
    maplelin
        144
    maplelin  
       2022-11-16 11:39:43 +08:00
    感觉这种具体业务的数据,如果有些其他关联性的结论用来剪枝就好了,毕竟人工可以得出解,算法的话应该有技巧可以优化的。
    diandian666
        145
    diandian666  
    OP
       2022-11-16 11:43:03 +08:00
    @maggch97 这组数据其实还有其他数据的。只是我在两个数组中,去掉两个数组都一样的值剩下的。估计我的数据确实是需要把相同属性的合并起来在匹配。后面已经贴出来没有去除两个数组相同的值且把数组 1 相同属性的合并起来后,再用你的代码匹配。确实成功了。真不错。666 啊
    maggch97
        146
    maggch97  
       2022-11-16 11:50:25 +08:00
    @diandian666 去掉相同的这个优化没有问题,问题是你的 1 数据不合并可能根本凑不出解
    Damn
        147
    Damn  
       2022-11-16 11:52:33 +08:00   ❤️ 1
    diandian666
        148
    diandian666  
    OP
       2022-11-16 11:52:59 +08:00
    @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]
    diandian666
        149
    diandian666  
    OP
       2022-11-16 11:53:55 +08:00
    @maggch97 哈哈,对的。我现在也怀疑这个,因为原题给的几组都是合并数组 1 的。
    maggch97
        150
    maggch97  
       2022-11-16 11:56:45 +08:00 via Android
    @diandian666 我上面说了,你 2 数组里只有一个 0.4 是凑不出 1 数组里的 0.96 和 1.52 的。你手算试试用 2 数组里面的数字去凑凑看,能不能凑出这两个数字
    A3
        151
    A3  
       2022-11-16 12:01:01 +08:00 via Android
    @EugeneYWang 我不是面试官🙈
    haichaofine32
        152
    haichaofine32  
       2022-11-16 12:16:31 +08:00 via Android
    好奇,这题能否反过来做?也就是给定一个数组,取任意个数值相加,看能得出多少不同的结果?猜测循环次数应该是折半的,例如九个数任取两个不重复,和九个数任取 7 个不重复是一个种状态。非专业,大佬忽喷
    diandian666
        153
    diandian666  
    OP
       2022-11-16 12:20:08 +08:00
    @maggch97 似乎还真是。大佬 666 ,
    Innovatino
        154
    Innovatino  
       2022-11-16 12:38:00 +08:00 via iPhone
    @diandian666 建议买杯咖啡给大佬🤣
    sdushn
        155
    sdushn  
       2022-11-16 14:01:51 +08:00
    回溯?
    bosskwei
        157
    bosskwei  
       2022-11-16 14:41:39 +08:00
    你这个问题很简单,实际上可以认为是一个近似矩阵乘法的操作。矩阵的 element 只有 0 或 1
    lyminghao
        158
    lyminghao  
       2022-11-16 15:01:04 +08:00
    相当于迭代地求解 subset sum 问题( 0-1 背包的一个变体),是 NP 完全的。

    当然自己写个搜索算法也 ok ,但是像这种难度的问题,还是建议试下用求解器解决。比如建模成一个 0-1 整数规划问题,送进 CPLEX ,Gurobi 直接就有答案了。

    如果人肉眼都能配出解来,那对这些求解器肯定是能秒出结果的。
    lyminghao
        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 匹配唯一
    mylove614
        160
    mylove614  
       2022-11-16 15:15:49 +08:00
    建议发在 icpc 或者 oi 的群里,大佬应该会给你答案的
    Nazz
        161
    Nazz  
       2022-11-16 15:32:28 +08:00
    以测试数据为例, 使用 dp 算法求出 3 组数据, 然后三层循环找出一个没有交集的组合
    SenseHu
        162
    SenseHu  
       2022-11-16 15:40:25 +08:00
    @diandian666 "不知道呢,一组数据是付款订单。另一组数据是移除订单。反正就是这两个不互通。需要自己匹配关联呢。"
    so 付款订单其实是由若干商品组合成,移除的时候可能单独移除了一两个,那付款订单其实把商品 id 带上的话,这个问题会简化很多?
    optional
        163
    optional  
       2022-11-16 15:57:04 +08:00 via iPhone
    @lyminghao 没有任何收敛条件,全是 01 变量,这能跑出来?
    diandian666
        164
    diandian666  
    OP
       2022-11-16 16:11:50 +08:00
    @SenseHu 两组数据的订单号全部是一样的呢。只是一组有地区,另一组没地区。需要匹配成功后,也把地区填充到另一组。
    binxin
        165
    binxin  
       2022-11-16 16:34:09 +08:00
    OP 主楼里面的两个 case 都解出来了,正要过来 show 一下,发现 op re 的那个长 case 报“maximum recursion depth exceeded”了。
    gold2022
        166
    gold2022  
       2022-11-16 16:38:09 +08:00
    nielinjie
        167
    nielinjie  
       2022-11-16 17:26:18 +08:00
    不是应该先采访下人工队是怎么做的么?
    Keen06
        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;
    }
    '''
    brader
        169
    brader  
       2022-11-16 18:32:11 +08:00
    我建议直接暴力穷举,因为既然人工能看的过来,不可能计算机穷举不完
    cnuser002
        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...

    这样参与最终匹配的数字降下来,你这个问题就能找出解。

    找出解以后,你再还原回去。
    lyminghao
        171
    lyminghao  
       2022-11-16 21:44:59 +08:00
    @optional 啥叫收敛条件... 搜索空间有限可数,肯定能跑出来啊
    zengguibo
        172
    zengguibo  
       2022-11-16 21:50:45 +08:00
    我觉得你可能漏了一些业务信息,这些数字靠人工很难凑出来的
    Building
        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
    mmdsun
        174
    mmdsun  
       2022-11-16 22:25:07 +08:00
    是不是这样?
    https://paste.ubuntu.com/p/R3W7vqkfjv/

    我还没开始减枝优化,发现基本上暴力都秒解。加了点小优化
    quxw
        175
    quxw  
       2022-11-17 00:21:29 +08:00   ❤️ 1
    写了一个,三个都能很快跑出来,是穷举优化了下.
    https://gist.github.com/quxiaowei/ccb676bf2b66a4b0f9a35b959e0e7d09
    hicdn
        176
    hicdn  
       2022-11-17 02:47:48 +08:00   ❤️ 1
    @quxw 的版本能行,就是算的太慢,风扇起飞。
    加上 cache 后,秒出结果。给递归加 cache ,常见的优化策略。

    https://gist.github.com/4ft35t/814b5ba8bba6cf1a2fc3dc14db818cb9
    superhxl
        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 的表示值和真实值误差最小
    optional
        178
    optional  
       2022-11-17 07:16:19 +08:00 via iPhone
    @superhxl 我看的懂你的模型,不用解释,关键是这个模型本质上就是暴搜,数量稍微大点,出不来的。
    optional
        179
    optional  
       2022-11-17 07:17:51 +08:00 via iPhone
    @optional m*n 个变量,每个变量两个状态,复杂度是 2^( m*n )
    zjsxwc
        180
    zjsxwc  
       2022-11-17 08:47:31 +08:00
    因为没有唯一解(最优解)所以不大会考虑直接用动态规划思路,
    于是考虑暴力搜索 dfs 、bfs 加 剪支。
    StrayBugs
        181
    StrayBugs  
       2022-11-17 08:52:58 +08:00 via Android
    凑硬币,先倒序排序,然后先凑大后凑小地 dfs 。
    acerphoenix
        182
    acerphoenix  
       2022-11-17 09:08:10 +08:00   ❤️ 1
    你这问题很难啊,解不是唯一的,而且还得考虑一个和数能用到这里,也能用到那里,但实际只能用到那里,但你先用到这里导致最后算不出来。
    weeei
        183
    weeei  
       2022-11-17 09:38:56 +08:00
    @dallaslu 不像是凑发票,还记得以前的 P2P 理财产品是怎么分配用户的资金吗?这个算法很 P2P 很像。
    xuelu520
        184
    xuelu520  
       2022-11-17 09:54:24 +08:00
    我第一想到是暴力递归,不过感觉还是有点难搞
    PinkLadyMage
        185
    PinkLadyMage  
       2022-11-17 10:22:19 +08:00
    这是资金盘 /互助系统的逻辑吗
    mystrylw
        186
    mystrylw  
       2022-11-17 11:21:54 +08:00
    这问题我一直用 excel 的规划求解做 数据量少一点还能跑 数据量大了 单线程跑半天
    xuxuzhaozhao
        187
    xuxuzhaozhao  
       2022-11-17 11:29:24 +08:00   ❤️ 1
    我喜欢这种问题,看完脑子有点痒,感觉要长脑子了。
    diandian666
        188
    diandian666  
    OP
       2022-11-17 12:09:14 +08:00
    @quxw 晚点,我测试下,这会有点忙,也没能及时回复大伙。
    diandian666
        189
    diandian666  
    OP
       2022-11-17 12:12:09 +08:00
    好多回复都没能及时。感谢各位热心回复的人儿啊。特别是那些提供建议或者代码的,棒棒的。晚点有空的时候,我在细溜各位的留言...再次感谢..
    dallaslu
        190
    dallaslu  
       2022-11-17 12:48:56 +08:00
    @quxw
    @hicdn
    有时会有陷阱的。比如 20+21+26 = 10+10+11+15+20 ,若先算出 20=10+10……
    dallaslu
        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 ,同样失败
    superhxl
        192
    superhxl  
       2022-11-17 13:14:49 +08:00 via Android
    @optional 爆搜不至于吧!前面很多人提的分枝、剪枝、深广度搜素实际都已经集成到求解器中,个人感觉肯定比自己搜要快!
    optional
        193
    optional  
       2022-11-17 13:21:55 +08:00 via iPhone
    @superhxl 你的约束模型得有剪枝空间才行,比如一个 LP 条件
    zer0fire
        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. 由此可以得到结果
    zer0fire
        195
    zer0fire  
       2022-11-17 14:17:40 +08:00
    @zer0fire 为解决数组 2 的最大公约数不等同与数组 1 的最大公约数, 可以先对数组 2 做逆序, 让最大的元素与其他的元素组合在一次成为最接近它的数组 1 的公倍数
    maggch97
        196
    maggch97  
       2022-11-17 15:28:32 +08:00
    不要期望找一个策略就能完全解决这个问题,要是真有 NP=P 就成立了。只有暴搜一条路,可以加暴搜+剪枝,暴搜+DP 稍微优化一下,不过这些优化对原问题都是杯水车薪。

    最终让上面所有代码跑起来的前提是,楼主的数据是人手都能凑出来的数据,说明了搜索空间里面解的占比非常大。
    bluefountain
        197
    bluefountain  
       2022-11-17 15:34:53 +08:00
    excel 的第三方插件能干这个
    bugmaker233
        198
    bugmaker233  
       2022-11-17 17:34:23 +08:00
    @xuxuzhaozhao 哈哈和我一样
    forty
        199
    forty  
       2022-11-17 17:55:29 +08:00
    生成 1 个接近的结果给人工去调整应该也能大大节省人工
    yuruizhe
        200
    yuruizhe  
       2022-11-17 19:58:45 +08:00 via iPhone
    @wfd0807 同+1
    dp[i][j]表示 a[0]~a[i]求和构成 j 的方案总数
    dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]]
    为每一个 j 求出候选集
    然后二分图,求完美匹配
    1  2  3  
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5440 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 37ms · UTC 08:53 · PVG 16:53 · LAX 01:53 · JFK 04:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.