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

一道算法题求助。

  •  
  •   letianqiu · 2018-04-29 12:41:42 +08:00 · 3738 次点击
    这是一个创建于 2161 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有 N 个物品,报价为[p1, p2, ..., pn]。一共有 N 个客户,每个客户对每件商品所能接受的价格是一个函数 C(i, j),i 是第 i 个客户,j 是第 j 件商品。现在要把这 N 件商品卖给这 N 个客户,每个客户只愿意够买一件商品,并且 C(i, j) <= pj 时,该客户才愿意购买该商品。求最大的销售收入是多少。
    ------------------------------------------------------------------------------------------------------------------------------------------------
    第一反应是把原问题分解为:将前 i 件商品卖给前 j 个客户时的最大收入是多少。但是继续想了以后发现,当 i > j 时,必然有商品没有卖出,但是该最优解并不一定包含在后续的最优解里。
    第 1 条附言  ·  2018-04-30 08:30:42 +08:00
    并且 C(i, j) >= pj 时,该客户才愿意购买该商品
    感谢各位,的确是带权二分图最大匹配。这题是我自己根据原来一道贪心题修改而想到的,之前并未接触过匈牙利算法和 KM 算法
    14 条回复    2018-05-01 11:17:47 +08:00
    htfy96
        1
    htfy96  
       2018-04-29 12:54:20 +08:00   ❤️ 1
    带权二分图最大匹配了解一下 当 i>j 时,增加 i-j 个 C(i, j)=0 的商品即可
    yhvictor
        2
    yhvictor  
       2018-04-29 12:56:11 +08:00 via iPhone
    估计是最大流相关算法。
    如果我没记错的话,最小费用流可解(不是最小费用最大流)。有没有最小割之类的解法不知道。
    taojing10
        3
    taojing10  
       2018-04-29 13:02:01 +08:00 via iPhone
    参考 leetcode 股票问题
    sengxian
        4
    sengxian  
       2018-04-29 13:26:27 +08:00
    @htfy96 本题并不一定要求一个完美匹配,即不完美匹配的权值可能大于完美匹配的权值,所以 KM 算法是不行的。
    @yhvictor 本题应该是一个最大费用流问题,即费用为负数时立刻停止增广。
    htfy96
        5
    htfy96  
       2018-04-29 13:52:02 +08:00
    @sengxian 楼主这个图是 K_{n, n}吧,边权非负情况下 max-weight matching 似乎一定是完备的?不然两边总能找到未匹配的点加进去形成更大 weight 的匹配
    sengxian
        6
    sengxian  
       2018-04-29 20:58:18 +08:00
    @htfy96 最大权匹配不一定完备,反例很容易构造。

    htfy96
        7
    htfy96  
       2018-04-29 21:15:15 +08:00
    @sengxian 但你这图不是 K_{n, n}啊,(p_2, n_2)之间边补上最大匹配就可以完备了
    sengxian
        8
    sengxian  
       2018-04-29 22:17:27 +08:00   ❤️ 2
    @htfy96 K_{n, n} 确实是对的。这个题把不能加买的物品价值设为 0,就是 K_{n, n} 了,那样就可以用 KM 了,刚才我光考虑到匹配的实际意义了。
    necomancer
        9
    necomancer  
       2018-04-29 22:34:56 +08:00
    先对价格排序,然后从最大价格商品起(不应该是 Cij >= Pj 才买么……),对 Ci 进行遍历,如果商品能重复卖出,那么所有能承受最大价格的都买下最大价格的商品,然后价格第二大的商品……
    s=0
    for p in sorted(P)[::-1]:
    ....for i,c in enumerate(Cij):
    ........if (p<=c).any():
    ............s += p
    ............Cij[i]=-1 # 买过一次就不能再买
    ............break # 如果商品也不能重复

    方法笨了点,我自己生成了几个好像可以……用的是 numpy 数组的写法。
    necomancer
        10
    necomancer  
       2018-04-29 22:54:07 +08:00
    嗯……也许可以更 numpy 一点:
    Cij = Cij[:, np.argsort(p)]
    p = p[np.argsort(p)] # 价格和接受能力从低到高排序
    d = (Cij - p) >0
    sum([p[_][-1] for _ in d]) #每个客户都买可接受的最贵产品。如果允许一个客户重复购买,不允许多个客户重复购买某商品是不是没意义……我有点脑残。
    lance6716
        11
    lance6716  
       2018-04-29 23:46:44 +08:00 via Android
    匈牙利算法,课本例题水平
    letianqiu
        12
    letianqiu  
    OP
       2018-04-30 08:28:52 +08:00
    @necomancer 没错,应该是 C(i, j) >= Pj
    18577347704
        13
    18577347704  
       2018-05-01 11:15:06 +08:00
    @lance6716 我想问问,您用的什么课本??我们学校只在数据结构里面穿插讲了点算法,没有专门的算法课。。。
    lance6716
        14
    lance6716  
       2018-05-01 11:17:47 +08:00 via Android
    @18577347704 这个是图论的…<图论及其应用>
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2814 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 14:43 · PVG 22:43 · LAX 07:43 · JFK 10:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.