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

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

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

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

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

    题目:

    有两组数字数组数据,数组 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  
    smallWang
        1
    smallWang  
       2022-11-15 17:47:56 +08:00
    这排列组合也太多了吧 你 N 的范围有确定吗? 人工作也挺痛苦的啊
    muchenlou
        2
    muchenlou  
       2022-11-15 17:48:16 +08:00   ❤️ 1
    好家伙,有点意思。下意识想到的是穷举
    diandian666
        3
    diandian666  
    OP
       2022-11-15 17:50:26 +08:00
    @smallWang N 的范围不确定的。这花了我两天时间写。后面举例的两组数据自己本地测试都能匹配成功。放到线上一跑,就有其他的匹配不成功(原题那组匹配不成功),虽然自己也知道问题出在哪,但是还是不懂怎么写下去了...
    tusj
        4
    tusj  
       2022-11-15 17:50:55 +08:00
    人工匹配的老哥,是真的有点牛逼。这 N 也没个限制,人工一般要匹配多久?
    w88975
        5
    w88975  
       2022-11-15 17:51:26 +08:00   ❤️ 5
    举例的话, 建议你拿一些简单的数字, 这眼睛都看花了
    lambdaq
        6
    lambdaq  
       2022-11-15 17:52:52 +08:00   ❤️ 13
    好家伙,搁这在对账呢。。。
    diandian666
        7
    diandian666  
    OP
       2022-11-15 17:55:12 +08:00
    @tusj 我前面也怀疑这人工怎么匹配。就原题那组,我匹配了 62.13 这个。剩下两个数字 26.67,17.76 我代码匹配不到。我发给他们人工匹配剩下两个数字。几分钟不到就给我匹配出来了。惊掉我下吧,不能发图,不然你们估计也惊掉下巴......
    dallaslu
        8
    dallaslu  
       2022-11-15 17:56:07 +08:00
    数据复杂了肯定存在不唯一的解……另外这是在凑发票吗?
    diandian666
        9
    diandian666  
    OP
       2022-11-15 17:56:20 +08:00
    @w88975 简单的数据,自己都可以按规则弄点简单的。但是代码跑可以用我提供的那几组。
    quan01994
        10
    quan01994  
       2022-11-15 17:56:46 +08:00
    第一感觉只能穷举啊 , ,,,,
    zqxjoe
        11
    zqxjoe  
       2022-11-15 17:57:05 +08:00
    @lambdaq 看起来还真像对账用的
    liyang5945
        12
    liyang5945  
       2022-11-15 17:57:07 +08:00
    你倒不如说下原始的需求
    pual
        13
    pual  
       2022-11-15 17:57:22 +08:00   ❤️ 1
    二分图匹配,匈牙利算法
    wangnimabenma
        14
    wangnimabenma  
       2022-11-15 17:57:35 +08:00
    这个运营得是研究生吧,我大专生可做不了这个
    wfd0807
        15
    wfd0807  
       2022-11-15 17:58:07 +08:00
    循环×动态规划
    diandian666
        16
    diandian666  
    OP
       2022-11-15 17:58:25 +08:00
    @lambdaq 这也可以说算是。他是匹配到了之后,用个字段关联起来的。相当于把数据关联起来。没有关联的字段。这也有运营的一个问题在这里。
    diandian666
        17
    diandian666  
    OP
       2022-11-15 17:59:56 +08:00
    @wfd0807 这是什么操作。我也是循环,递归,最终还是发现问题解决不了...有空可以试下,当作自己的锻炼啥也行,帮助我这个准备被 IT 淘汰的也好。哈哈哈
    diandian666
        18
    diandian666  
    OP
       2022-11-15 18:00:33 +08:00
    @dallaslu 不是凑发票。就是亚马逊运营的数据需要关联起来。
    diandian666
        19
    diandian666  
    OP
       2022-11-15 18:01:38 +08:00
    @liyang5945 需求就是 两组数据。进行匹配呢,我得到的需求也是这样。只不过我能找到这两组数据,我提供出来而已。
    diandian666
        20
    diandian666  
    OP
       2022-11-15 18:02:06 +08:00
    @pual 这好高级啊。听都没听过。擦....尴尬。大佬求教
    jiangzm
        21
    jiangzm  
       2022-11-15 18:02:53 +08:00
    @wangnimabenma 逗笑我了
    zxcslove
        22
    zxcslove  
       2022-11-15 18:03:02 +08:00   ❤️ 2
    感觉和库存棒材的切割优化方案很像
    jukka
        23
    jukka  
       2022-11-15 18:04:02 +08:00   ❤️ 1
    典型的背包问题。搜 背包九讲, 看下哪个合适你的场景。
    SimonOne
        24
    SimonOne  
       2022-11-15 18:04:19 +08:00
    数组 1[1,2]
    数组 2[0.1,0.2,0.3,0.7,0.8,0.9]

    按你的匹配法有多个解,你想哪个呢?
    jiangzm
        25
    jiangzm  
       2022-11-15 18:07:06 +08:00
    @diandian666 反推成功也不一定是真实的组合, 不太明白你们用这个意义在哪。 还有从亚马逊运营数据为啥两份数据没有共同的标识关联。
    diandian666
        26
    diandian666  
    OP
       2022-11-15 18:07:10 +08:00
    @SimonOne 只要其中一个解就行了。不用全部解
    lakehylia
        27
    lakehylia  
       2022-11-15 18:07:45 +08:00
    你这不就是简化成从一堆数据里面挑出 N1 个数,使和为 A1 ,然后把剩下的数挑出 N2 个数,使和为 A2 。如果中间失败了,就剪枝
    diandian666
        28
    diandian666  
    OP
       2022-11-15 18:08:16 +08:00
    @jiangzm 不知道呢,一组数据是付款订单。另一组数据是移除订单。反正就是这两个不互通。需要自己匹配关联呢。
    diandian666
        29
    diandian666  
    OP
       2022-11-15 18:09:40 +08:00
    @lakehylia 是这个道理。道理懂了,代码拉了,尴尬。
    diandian666
        30
    diandian666  
    OP
       2022-11-15 18:10:33 +08:00
    @zxcslove 嗯嗯嗯呢。
    SimonOne
        31
    SimonOne  
       2022-11-15 18:11:41 +08:00
    用遍历感觉会死,比如
    数组 1[1,2,3]
    数组 2[01,0.9,1.9,2.1,0.2,0.8]

    用遍历的话,出来 1=0.1+0.9 ,结果后面 2 和 3 就遍历不出来了 😂
    diandian666
        32
    diandian666  
    OP
       2022-11-15 18:13:38 +08:00
    @SimonOne 这就要重新算了。也难道我了。遍历,递归,剔除 都用了。我最后也只能匹配后面举例的两组数据,原题的那组没成功。知道问题在哪里,但是写不动了...
    diandian666
        33
    diandian666  
    OP
       2022-11-15 18:15:16 +08:00
    @jukka 搜嘎,写基础代码久了,很多没都没听过。我去了解了解... ~~~///(^v^)\\\~~~
    maggch97
        34
    maggch97  
       2022-11-15 18:16:01 +08:00
    这点数据量,搜索+减枝呗,搜不出来是你写错了。又不用考虑出题人会给一万个 0.01 数据。
    maggch97
        35
    maggch97  
       2022-11-15 18:17:43 +08:00
    @jukka 这是典型的背包?
    totatx
        36
    totatx  
       2022-11-15 18:18:30 +08:00   ❤️ 1
    akaHenry
        37
    akaHenry  
       2022-11-15 18:19:01 +08:00
    你这运营数据有点意思.

    你可能需要使用 python + pandas 之类的工具, 来写个统计+计算脚本, 可能很快.

    提供一个粗糙的思路:

    1. 2 组数据, 先排序(小<大).
    2. 数组 2 数据, 计算一些特征值(暂存):
    重复值先 count 计数, 并 sum() 部分值.
    计算数组 2 的 均值, 众数. 并作为后续遍历的结束条件.

    3. 因为数组 1, 是由 数组 2 构造的. 比如 17.76, 必然由 < 17.76 的数组合成(废话). 遍历时, 可以剔除 > 17.76 的值.
    结合 二分法 + 遍历, 应该不需要完全遍历.

    数组 1 排在前面的计算结果, 也是 后面的值的一部分.

    按照这个思路, 应该可以写一个能用的算法. 哈哈
    diandian666
        38
    diandian666  
    OP
       2022-11-15 18:20:59 +08:00
    @jukka 看了 背包九讲 9 个例子都和我的需求不一样呢...继续求高人指点...
    SimonOne
        39
    SimonOne  
       2022-11-15 18:22:49 +08:00
    @akaHenry #36 😂 幸好是订单,值肯定是正数(至少是非负数),不然遍历时还不能剔除 > 17.76 的值
    jukka
        40
    jukka  
       2022-11-15 18:23:47 +08:00
    不是完全一样的,背包去掉 cost ,weight 不取 max ,去相等,就是你这个问题了吧
    hsfzxjy
        41
    hsfzxjy  
       2022-11-15 18:23:54 +08:00 via Android
    数据量有多大?这决定你能接受的时间复杂度下限
    jetvster
        42
    jetvster  
       2022-11-15 18:24:20 +08:00
    先分组,再递归,复杂度应该不高
    wzy44944
        43
    wzy44944  
       2022-11-15 18:24:40 +08:00 via Android
    问下做人工匹配的人有什么经验?
    ZRS
        44
    ZRS  
       2022-11-15 18:24:48 +08:00 via iPhone
    变种传输问题,不会有复杂度很低的解法。建议从业务方向入手
    CEBBCAT
        45
    CEBBCAT  
       2022-11-15 18:25:02 +08:00 via iPhone
    根据楼主的描述,好像不存在唯一解。楼主清楚的吧?
    diandian666
        46
    diandian666  
    OP
       2022-11-15 18:25:08 +08:00
    @totatx 这个地址的需求和我的还是有区别的。我这需求的是需要数组 2 全部用上且只用 1 次匹配数组 1.
    diandian666
        47
    diandian666  
    OP
       2022-11-15 18:26:45 +08:00
    @maggch97 大佬尝试一下?
    jukka
        48
    jukka  
       2022-11-15 18:27:53 +08:00
    仔细想了下,不太对,这里没有状态转换,数据量不大单纯的暴力搜索应该能出结果,想复杂了。
    betatabe
        49
    betatabe  
       2022-11-15 18:28:17 +08:00
    人工匹配的算法不就是现成的算法吗,直接问问咋匹配的不就指导了(指数复杂度的算法,人工几分钟算出来只能说有丶东西)
    diandian666
        50
    diandian666  
    OP
       2022-11-15 18:29:12 +08:00
    @hsfzxjy 线上运行的时候,直接就发现数组 2 的数据有 80+个。组 1 也有十个左右。我合并了组 1 相关的,才变成几个
    diandian666
        51
    diandian666  
    OP
       2022-11-15 18:30:00 +08:00
    @betatabe 我刚还真去问了为啥这么快就能匹配。他们说随便看看就匹配出来了,无规则....
    diandian666
        52
    diandian666  
    OP
       2022-11-15 18:30:57 +08:00
    @jukka 数组 1 大概 10 个以内。数组二 100 个以内。这样的规模
    betatabe
        53
    betatabe  
       2022-11-15 18:31:59 +08:00
    @diandian666 第一个例子这种随便看看匹配出来?
    maggch97
        54
    maggch97  
       2022-11-15 18:32:14 +08:00
    @hsfzxjy 我给你个写法思路吧,把第二个数组修改成[[value1, count1], [value2, count2], ... ], 把相同的数字合并在一起。dfs 的时候去枚举 count

    如果你 1 也有重复,也能减枝。不过我觉得我上面说的对于你这个数据量完全够了
    jiangzm
        55
    jiangzm  
       2022-11-15 18:34:04 +08:00
    你的这些数字是有特征的, 所以前面有同学说走业务方向参考人工经验是对的。
    再加上一些历史组合优先考虑, 应该能降低一点复杂度和计算量
    jiangzm
        56
    jiangzm  
       2022-11-15 18:34:52 +08:00
    @betatabe 小看了人工的历史经验
    diandian666
        57
    diandian666  
    OP
       2022-11-15 18:35:04 +08:00
    @akaHenry 大佬的回答。我也是根据大小先倒序。从数组 1 最大的开始匹配数组 2 最大的开始。数组 2 一直往下加,超出数据就剔除。最终也是能实现上面题目末尾的两组数据。原题的那组失败了,因为原题那组需要剔除中间的值,这个剔除超乎我的想象,数据太大了
    jaggle
        58
    jaggle  
       2022-11-15 18:35:41 +08:00
    B 中的数字能有剩余吗?
    MMMMMMMMMMMMMMMM
        59
    MMMMMMMMMMMMMMMM  
       2022-11-15 18:36:41 +08:00   ❤️ 4
    你与业务团队大概是信息不对称

    他们能人工匹配出来,说明可能有订单相关的 id 之类(根据 id 反查直接已经有结果列表了,然后人工加总而已)

    你在做的很可能是无用功,去问问吧
    diandian666
        60
    diandian666  
    OP
       2022-11-15 18:36:52 +08:00
    @jaggle 不可以,要全部使用。因为数组 1 的总和刚好等于数组 2 的
    jaggle
        61
    jaggle  
       2022-11-15 18:37:26 +08:00
    所以真的存在人脑能算,但是计算机算不出来的题目吗,2333
    betatabe
        62
    betatabe  
       2022-11-15 18:38:15 +08:00
    所以肯定有额外的输入信息,被 op 忽略了,仅靠两个数组去求解复杂度就是指数级的
    diandian666
        63
    diandian666  
    OP
       2022-11-15 18:39:10 +08:00
    @jaggle 估计人脑也是乱串算对的。代码也行的,我的代码问题也发现知道哪里有问题,但是没能还没找到突破
    jaggle
        64
    jaggle  
       2022-11-15 18:39:36 +08:00
    @diandian666 哦,对,间接需求导致 B 中无剩余的数字
    jaggle
        65
    jaggle  
       2022-11-15 18:42:29 +08:00
    应该是什么券包之类的场景吧,比如 系统今天发了 n 个 金额总计 x 元的券包,里面包含 x1,x2,xn....的券,求券和券包的对应关系(所以为什么不用关系型数据库!)
    jiangzm
        66
    jiangzm  
       2022-11-15 18:42:45 +08:00
    业务系统是会避免产生数据孤岛的, 大概率是你没找到关联信息, 从源头拿数据吧,不要从二贩子(业务人员导出的?)拿数据
    maggch97
        67
    maggch97  
       2022-11-15 18:42:50 +08:00 via Android
    @diandian666 我回家有时间给你写个代码吧,这么多贴子居然全在扯淡
    aijam
        68
    aijam  
       2022-11-15 18:50:22 +08:00   ❤️ 5
    xuanbg
        69
    xuanbg  
       2022-11-15 18:54:06 +08:00
    首先,你这个数字只能用一次,所以不是全组合。这样组合数其实非常少。而且大于集合 1 里面的数字的组合可以直接排除,那组合数就更少了。
    OP 你的逻辑肯定没有优化好,我估计递归深度应该不会超过集合 2 的个数的平方。
    meeop
        70
    meeop  
       2022-11-15 18:58:18 +08:00
    暴力穷举吧,既然人工能做到匹配,说明计算量不大,计算机一定能完成,不行堆机器
    这个问题据我理解是没有 o(n^2)以下算法解的,可能可以通过动态规划优化下性能

    这个其实就是素数分解,如果有快速算法解的话,非对称加密就被破解了
    weiwoxinyou
        71
    weiwoxinyou  
       2022-11-15 18:59:27 +08:00 via Android
    看了一下测试数据,有很多相同的小数,然后你汇总的值有小数点尾数为奇数的,这就意味着如果一个大数+一个尾数为奇数的值必定来源于一个或多个奇数尾数值加和,这个可以作为优先匹配方法。
    在匹配完所有尾数为奇数的数值完全匹配后,算数组一的两数差,由于每一个值与其余值差必定对应数组二中数字,这样可以凑出另一部分的数据。
    剩下的可以直接穷举了
    jukka
        72
    jukka  
       2022-11-15 19:00:41 +08:00
    内存循环是 0-1 背包问题。
    这个问题暴力搜索的话,应该是 2^n 复杂度,不是 n^2 。
    ywl19891989
        73
    ywl19891989  
       2022-11-15 19:02:56 +08:00
    排序之后倒序走。从最小的开始。穷举应该也可以的
    Damn
        74
    Damn  
       2022-11-15 19:03:37 +08:00
    xuanbg
        75
    xuanbg  
       2022-11-15 19:06:11 +08:00
    解题思路是这样的:
    先将集合 1 排序,从最小的数字开始凑。能凑出来的就是一棵树的根。
    然后每个根开始用剩下的数凑第二大的数,每个能凑出来的组合就是这个根下的第二层子节点。
    以此类推,凑下一个数,所有的组合形成下一层子节点。
    从如果凑的过程中遇到凑不出来的,那么这棵树就可以删掉了。

    综上所述,树的高度等于集合 1 的数字个数,树的数量取决于能凑出几个组合。
    shyrock
        76
    shyrock  
       2022-11-15 19:08:40 +08:00
    简单说就是遍历数组 2 ,把其中每一个数尝试分配到数组 1 的某一个框里面。分配完之后检查每个框的小计等不等于代表这个框的数字。

    如果不做任何优化剪枝,纯暴搜的话时间复杂度是 O(m^n)?
    dallaslu
        77
    dallaslu  
       2022-11-15 19:10:30 +08:00
    既然人肉算法一定能求出结果……我有个不成熟的想法。

    我们把这个问题做个比喻,有多只大小不一的瓶子,里面装着大小不一石子和水,水面与平口持平,现在把所有石子捞出来混在一起,让一只强迫症乌鸦把石子装回去。

    把瓶子和石子按大小依次排列,先扔大石子,后小石子,保证过程中水不溢出,直到某个石子 X 没有瓶子可投,此时从瓶子捞出适量的石头 Y (体积大于等于瓶中剩余体积+X 的体积)直到把这个石子投进去,最终投完。

    困难的部分在于“捞出适量的石头 Y”这一步,应当设定一些原则,比如尽量捞出被置换次数较少的石头,尽量选择 Y 数量少的瓶子,以避免石子的分配方案变化过少出现死局。

    基于这些设定,即使最开始的一批大石头位置放错,导致未能求出解,也能被置换石头的过程修正。
    xuanbg
        78
    xuanbg  
       2022-11-15 19:11:59 +08:00
    @xuanbg 如果深度优先进行递归的话,只要能生成一棵高度等于集合 1 数字个数的树,你就已经找到解了。
    dallaslu
        79
    dallaslu  
       2022-11-15 19:13:11 +08:00
    @dallaslu 当然复杂度爆炸哈哈,如果程序在限定的尝试次数内跑不出结果,建议转交给人工队解决
    optional
        80
    optional  
       2022-11-15 19:18:12 +08:00
    给个傻的方案吧:
    假设左边数组为 M(m 个数字),右边数组为 N(n 个数字)
    第一步:右边数组有 2^n 个排列组合(0~n 个数字),枚举排列这个组合,去掉和不在左边的组合(这一步左边可以直接做一个 set ,所以这一步复杂度有 2^n 。假设得到 K 个组合。
    第二步:对 K 这个组合选择 m 个,这里是 C(m,n)个选型,继续枚举它,通过并查集剪掉包含重复数字的(这一步存在优化空间)
    第三步:在第二部 C(m,n)就能找到结果了(如果存在)
    optional
        81
    optional  
       2022-11-15 19:22:03 +08:00
    撤回:第二步开始错了,首先没必要用并查集,直接判断 index 是否冲突就行,另外判断是否全等左边的可以在修改下,等会想到了回复。
    yorkyoung
        82
    yorkyoung  
       2022-11-15 19:22:34 +08:00

    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
        83
    AkashicRecords  
       2022-11-15 19:26:21 +08:00   ❤️ 15
    是个多背包问题的变体。
    Timus 上的 1394. Ships. Version 2 ,基本上和 OP 的问题是完全一致的了,Tag 是 hardest problem ,所以完全不用灰心做不出来。
    虽然没有直接的题解,可以看看评论区的讨论 https://acm.timus.ru/forum/?space=1&num=1394
    alalida
        84
    alalida  
       2022-11-15 19:33:40 +08:00 via Android   ❤️ 1
    考虑简单情况

    1,2,3,4

    3,7

    那就有两个解了 3-1,2 7-3,4
    或者 3-3 7-1,2,4
    aqqwiyth
        85
    aqqwiyth  
       2022-11-15 19:33:42 +08:00
    这个是从 总返利里面, 推算返利订单列表?
    optional
        86
    optional  
       2022-11-15 19:34:38 +08:00
    @optional

    假设左边数组为 M(m 个数字),右边数组为 N(n 个数字)
    第一步:右边数组有 2^n 个排列组合(0~n 个数字),枚举排列这个组合,去掉和不在左边的组合(这一步左边可以直接做一个 set ,所以这一步复杂度有 2^n 。假设得到 K 个组合,并在判断过程中分组,分组键为他们的和,
    得到一个 map ,注意这里它的 value 应存数字的下标,而不是数字本身,命名为 indexesBySum 。
    第二步:得到上一个 map ,按照 value 的数量排序,从数量最小的 key 出发,再遍历一次,不过这里每个 key 都要选择一个,然后如果 value 里面的下标已经用过的话,就跳过这个组合,应该就能得到答案了,如果只要其中一个就提前 return 。
    alalida
        87
    alalida  
       2022-11-15 19:35:21 +08:00 via Android
    感觉这题没有多项式时间解
    optional
        88
    optional  
       2022-11-15 19:35:49 +08:00
    这里估一下复杂度,看起来是 C(2^n,m) 嗯,复杂度可真高
    majormei
        89
    majormei  
       2022-11-15 19:37:19 +08:00
    @optional 我最开始也是一样的思路,看到第一个例子的数组长度 90 ,估计是没法跑起来了……
    akaHenry
        90
    akaHenry  
       2022-11-15 19:37:28 +08:00
    @aijam 68L, 已经给出了答案.

    跑了一下示例数据, 没啥问题.
    WngShhng
        91
    WngShhng  
       2022-11-15 19:39:47 +08:00   ❤️ 3
    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
        92
    optional  
       2022-11-15 19:43:22 +08:00
    @majormei 所以是个傻的办法,第一步产生了大量的冗余计算,忽略它吧
    tiedan
        93
    tiedan  
       2022-11-15 19:57:20 +08:00
    背包问题
    wxf666
        94
    wxf666  
       2022-11-15 20:03:04 +08:00
    @aijam 为嘛我改成楼主第一组数据(最长的那组),跑不出结果呢?

    显示:ans = {6213: [], 2667: [], 1776: []}
    frodez
        95
    frodez  
       2022-11-15 20:09:28 +08:00
    @diandian666 你看一下 83L 。
    PeterD
        96
    PeterD  
       2022-11-15 20:16:13 +08:00
    leetcode 0322
    ![solute](//i.imgur.com/j4UtApC.png)
    sarvatathagata
        97
    sarvatathagata  
       2022-11-15 20:25:58 +08:00   ❤️ 5
    不被难倒就怪了,这明显是 NP 完全的。不知道上面这些回复要自己造这么多表现一看就非常差的轮子是干嘛,人家 wiki 上已经写了那么多近似算法了,这已经是一个被研究得很多的问题了。https://en.wikipedia.org/wiki/Balanced_number_partitioning
    geelaw
        98
    geelaw  
       2022-11-15 20:31:52 +08:00
    @sarvatathagata #97 应该强调是 strongly NP hard ,这可以排除对伪多项式时间(动态规划解背包这种算法)的期待。
    vance123
        99
    vance123  
       2022-11-15 20:46:42 +08:00 via Android
    第一眼 NP ,第二眼背包。已经不知道是第多少次看到有人问 NP 的问题了
    vance123
        100
    vance123  
       2022-11-15 20:47:55 +08:00 via Android
    当然,每次都有不少人试图用各种奇巧淫计解决 NP 问题
    1  2  3  
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3400 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 10:38 · PVG 18:38 · LAX 03:38 · JFK 06:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.