一道算法题求助。 - V2EX
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
请不要在答技术问题时复制粘贴 AI 生成的内容
letianqiu
V2EX    程序员

一道算法题求助。

  •  
  •   letianqiu 2018-04-29 12:41:42 +08:00 4261 次点击
    这是一个创建于 2789 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有 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
    /div>
    @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     Solana     1082 人在线   最高记录 6679       Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 36ms UTC 18:08 PVG 02:08 LAX 10:08 JFK 13:08
    Do have faith in what you're doing.
    ubao msn snddm index pchome yahoo rakuten mypaper meadowduck bidyahoo youbao zxmzxm asda bnvcg cvbfg dfscv mmhjk xxddc yybgb zznbn ccubao uaitu acv GXCV ET GDG YH FG BCVB FJFH CBRE CBC GDG ET54 WRWR RWER WREW WRWER RWER SDG EW SF DSFSF fbbs ubao fhd dfg ewr dg df ewwr ewwr et ruyut utut dfg fgd gdfgt etg dfgt dfgd ert4 gd fgg wr 235 wer3 we vsdf sdf gdf ert xcv sdf rwer hfd dfg cvb rwf afb dfh jgh bmn lgh rty gfds cxv xcv xcs vdas fdf fgd cv sdf tert sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf shasha9178 shasha9178 shasha9178 shasha9178 shasha9178 liflif2 liflif2 liflif2 liflif2 liflif2 liblib3 liblib3 liblib3 liblib3 liblib3 zhazha444 zhazha444 zhazha444 zhazha444 zhazha444 dende5 dende denden denden2 denden21 fenfen9 fenf619 fen619 fenfe9 fe619 sdf sdf sdf sdf sdf zhazh90 zhazh0 zhaa50 zha90 zh590 zho zhoz zhozh zhozho zhozho2 lislis lls95 lili95 lils5 liss9 sdf0ty987 sdft876 sdft9876 sdf09876 sd0t9876 sdf0ty98 sdf0976 sdf0ty986 sdf0ty96 sdf0t76 sdf0876 df0ty98 sf0t876 sd0ty76 sdy76 sdf76 sdf0t76 sdf0ty9 sdf0ty98 sdf0ty987 sdf0ty98 sdf6676 sdf876 sd876 sd876 sdf6 sdf6 sdf9876 sdf0t sdf06 sdf0ty9776 sdf0ty9776 sdf0ty76 sdf8876 sdf0t sd6 sdf06 s688876 sd688 sdf86