一道算法题求助。

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2411 天前的主题，其中的信息可能已经有所发展或是发生改变。

有 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

2018-04-29 12:54:20 +08:00

带权二分图最大匹配了解一下当 i>j 时，增加 i-j 个 C(i, j)=0 的商品即可

yhvictor

2018-04-29 12:56:11 +08:00 via iPhone

估计是最大流相关算法。
如果我没记错的话，最小费用流可解(不是最小费用最大流)。有没有最小割之类的解法不知道。

taojing10

2018-04-29 13:02:01 +08:00 via iPhone

参考 leetcode 股票问题

sengxian

2018-04-29 13:26:27 +08:00

@htfy96 本题并不一定要求一个完美匹配，即不完美匹配的权值可能大于完美匹配的权值，所以 KM 算法是不行的。
@yhvictor 本题应该是一个最大费用流问题，即费用为负数时立刻停止增广。

htfy96

2018-04-29 13:52:02 +08:00

@sengxian 楼主这个图是 K_{n, n}吧，边权非负情况下 max-weight matching 似乎一定是完备的？不然两边总能找到未匹配的点加进去形成更大 weight 的匹配

sengxian

2018-04-29 20:58:18 +08:00

@htfy96 最大权匹配不一定完备，反例很容易构造。

htfy96

2018-04-29 21:15:15 +08:00

@sengxian 但你这图不是 K_{n, n}啊，(p_2, n_2)之间边补上最大匹配就可以完备了

sengxian

2018-04-29 22:17:27 +08:00

@htfy96 K_{n, n} 确实是对的。这个题把不能加买的物品价值设为 0，就是 K_{n, n} 了，那样就可以用 KM 了，刚才我光考虑到匹配的实际意义了。

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

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

2018-04-29 23:46:44 +08:00 via Android

匈牙利算法，课本例题水平

letianqiu

2018-04-30 08:28:52 +08:00

@necomancer 没错，应该是 C(i, j) >= Pj

18577347704

2018-05-01 11:15:06 +08:00

@lance6716 我想问问，您用的什么课本？？我们学校只在数据结构里面穿插讲了点算法，没有专门的算法课。。。

lance6716

2018-05-01 11:17:47 +08:00 via Android

@18577347704 这个是图论的…<图论及其应用>