V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Wolfsin
V2EX  ›  问与答

算法题写不出来,不知道有没有大佬给个思路。

  •  
  •   Wolfsin · 2021-01-05 15:40:45 +08:00 · 1227 次点击
    这是一个创建于 1408 天前的主题,其中的信息可能已经有所发展或是发生改变。

    跟分餐桌很像,但是写了半天还是写不出来。


    描述: 餐厅有 n 张桌子,每张桌子分别可以坐 a[n]个人,今日有 m 组客人预约,每组分别有 b[m]人。对其安排座位。 -如果:

    • 一组客人都安排在一张桌子上,那么满意度不会下降。
    • 如果拒绝这组客人的预约,那么满意度下降:人数 * x
    • 如果将一组客人分在 k 张桌子上用餐,那么满意度下降:(k-1) * y
      • 比如说有 4 人桌,5 人桌,1 人桌,1 人桌 4 张桌子,y=10 的情况下,将 7 人的一组客人,分到 4,5 2 张桌子的情况,满意度下降(2-1) * 10 。或者将其分成 5,1,1 3 张桌子的情况,满意度下降(3-1) * 10 。
    • 不能与其他组的客人拼桌

    输入形式: n m x y a[1] a[2] … a[n] b[1] b[2] … b[n]

    例 1:

    输入:
    4 2 5 3 
    4 5 1 1
    7 3
    输出
    6 ( 7 人组:分到 5 1 1 桌上,3 人组分到 4 人桌上)
    

    例 2:

    输入
    4 2 2 16
    4 5 1 1
    7 3
    输出
    14 ( 7 人组:拒绝预约,3 人组:分到 4 人桌上)
    

    例 3:

    输入
    4 2 5 3
    1 1 2 3
    2 5
    输出
    6 ( 2 人组:1,1 桌上,5 人组:分到 2,3 人桌上)
    
    第 1 条附言  ·  2021-01-05 19:38:12 +08:00
    数据范围:
    0<n<14,
    0<m<21,
    0<x,y<1001
    1<a[n],b[m]<1001
    均为整数
    第 2 条附言  ·  2021-01-06 22:54:51 +08:00
    LRvx #15
    yzbythesea #18
    谢谢 2 位大佬的解答
    19 条回复    2021-01-06 13:00:35 +08:00
    LRvx
        1
    LRvx  
       2021-01-05 19:31:18 +08:00
    有数据范围吗
    Wolfsin
        2
    Wolfsin  
    OP
       2021-01-05 19:39:36 +08:00
    @LRvx #1 在附言里更新了
    yzbythesea
        3
    yzbythesea  
       2021-01-05 19:55:03 +08:00
    m 和 n 也不大,直接 DFS,从人数最多的预约开始安排,安排完再搞次多的,依此类推。
    Wolfsin
        4
    Wolfsin  
    OP
       2021-01-05 20:02:49 +08:00
    @yzbythesea #3 之前也有从最多的人数开始安排的打算,但是看到例 2 后发现,有直接舍弃掉一组人的最优解,所以一下又没有想法了。
    他不是在求一组人的最优解,是在求几组人合在一起的最优解。想到这思绪就理不清楚了。如果可以的话,能不能提供点伪代码,或者更加具体的思路啊
    Wolfsin
        5
    Wolfsin  
    OP
       2021-01-05 20:11:11 +08:00
    @yzbythesea #3 根据 x 和 y 的数值,也会产生新的变化,如果不考虑 x 和 y 的话,7 人的最佳排法肯定是 5+4,考虑到下一组有 3 人,那么这么排就需要拒绝掉 3 人(满意度下降( 2-1 )*y+3*x );或者说 7 人采取次佳的排法 5+1+1,下一组可以排 4 人的那张桌子(例 1,满意度下降( 3-1 )*y );但是在例 2 中,x 远小于 y,这时候例 1 的排法就不是最优解了(例 2 的情况,满意度下降 7*x )。
    xupefei
        6
    xupefei  
       2021-01-05 20:13:17 +08:00
    应该是三维动态规划
    xupefei
        7
    xupefei  
       2021-01-05 20:20:21 +08:00 via iPhone
    又想了想,这不就是 fractional multiple knapsack 么
    LRvx
        8
    LRvx  
       2021-01-05 20:41:49 +08:00
    想一想,n 和 m 的范围不大,是状态压缩后做 dp 吗
    Wolfsin
        9
    Wolfsin  
    OP
       2021-01-05 20:51:31 +08:00
    @xupefei #7 的确应该算背包问题,但是贪心算法在这里并不是很好用。
    @LRvx #8 dp 我也考虑了一下,最后因为时间不够了没有仔细想下去。
    我最后的思路只剩下去算全部的可能性和其对应的下降值,但是写的途中也遇到了问题,因为理不清楚顺序,如果是不考虑复杂度,只是暴力去解的话,代码应该怎么写比较好呢?
    yzbythesea
        10
    yzbythesea  
       2021-01-05 21:18:16 +08:00   ❤️ 1
    @Wolfsin 对于任何一个组,我们可以算出需要几个桌子,然后从而得到拒绝这个组还是分开坐,花费高,然后进行选择。从人数最多的组开始。类似贪心。
    Wolfsin
        11
    Wolfsin  
    OP
       2021-01-05 21:26:20 +08:00
    @yzbythesea #10 但是还有一个问题,就是贪心是通过局部最优解来导出全体最优解,这里全体最优解可能不是局部的最优解,比如例 1 的人数最多 7 人组,计算出的最优解应该是 5+4,2 张桌子,满意度下降( 2-1 )*y ;但是实际的全体最优解却是 5+1+1,满意度下降( 3-1 )*y,至于为什么不选 5+4 的最优解,是因为下一组的关系。所以单纯按组贪心,还是算不出答案
    LRvx
        12
    LRvx  
       2021-01-05 21:44:46 +08:00
    老哥有评测姬的地址吗?
    LRvx
        13
    LRvx  
       2021-01-05 21:55:25 +08:00
    写了一个 dp ( 01 背包)+状压的解,但是目前手太生了,脑子也不行了,我测一测,看看对不对
    Wolfsin
        14
    Wolfsin  
    OP
       2021-01-05 22:16:59 +08:00
    @LRvx #13 抱歉,没有 oj,只能脑测。如果可以的话,能分享一下代码吗?
    LRvx
        15
    LRvx  
       2021-01-05 22:28:20 +08:00   ❤️ 1
    https://paste.ubuntu.com/p/VtbXNNyHGm/ 这个算法的复杂度在那个枚举每个状态的地方,所以时间复杂的有点大,实际上可以进行 sort 每种座子后根据一些规则进行筛选枚举每个组的不同安排情况,降低复杂度。
    yzbythesea
        16
    yzbythesea  
       2021-01-06 03:17:32 +08:00
    @Wolfsin 例子 1 先算 7 桌,肯定不会拒绝,然后安排可以是 5 + 4 也可以是 5 + 1 + 1 。再分别 DFS,5 + 4 这个只剩 1 + 1,对于 3 人 只能拒绝,得出 cost ; 5 + 1 + 1 只剩 4, 对于 3 人, 可以拒绝 也可以 安排, 算出 cost,完事儿。

    这个不是贪心,你还是得 DFS,只是基于贪心的概念进行剪枝。我觉得你不剪枝都可以,反正 m 和 n 都不大。
    yzbythesea
        17
    yzbythesea  
       2021-01-06 03:19:43 +08:00
    @yzbythesea 对于拒绝和安排,只能这两个大方向剪枝,不能对安排的策略剪枝。
    yzbythesea
        18
    yzbythesea  
       2021-01-06 09:02:44 +08:00   ❤️ 1
    写了一下 DFS 的方法,跑了三个例子都对,不知道还有没有别的例子。没有从最多的人数的组开始安排,也可以。

    https://paste.ubuntu.com/p/cnbZqjqWwY/
    Wolfsin
        19
    Wolfsin  
    OP
       2021-01-06 13:00:35 +08:00
    @LRvx #15
    @yzbythesea #18
    谢谢楼上 2 位大佬的解答
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5403 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 03:43 · PVG 11:43 · LAX 19:43 · JFK 22:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.