一道算法题求助。

[letianqiu]

有 N 个物品，报价为[p1, p2, ..., pn]。一共有 N 个客户，每个客户对每件商品所能接受的价格是一个函数 C(i, j)，i 是第 i 个客户，j 是第 j 件商品。现在要把这 N 件商品卖给这 N 个客户，每个客户只愿意够买一件商品，并且 C(i, j) <= pj 时，该客户才愿意购买该商品。求最大的销售收入是多少。
------------------------------------------------------------------------------------------------------------------------------------------------
第一反应是把原问题分解为：将前 i 件商品卖给前 j 个客户时的最大收入是多少。但是继续想了以后发现，当 i > j 时，必然有商品没有卖出，但是该最优解并不一定包含在后续的最优解里。

并且 C(i, j) >= pj 时，该客户才愿意购买该商品
感谢各位，的确是带权二分图最大匹配。这题是我自己根据原来一道贪心题修改而想到的，之前并未接触过匈牙利算法和 KM 算法

[htfy96]

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

[yhvictor]

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

[taojing10]

参考 leetcode 股票问题

[sengxian]

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

[htfy96]

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

[sengxian]

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

[htfy96]

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

[sengxian]

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

[necomancer]

先对价格排序，然后从最大价格商品起（不应该是 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]

嗯……也许可以更 numpy 一点:
Cij = Cij[:, np.argsort(p)]
p = p[np.argsort(p)] # 价格和接受能力从低到高排序
d = (Cij - p) >0
sum([p[_][-1] for _ in d]) #每个客户都买可接受的最贵产品。如果允许一个客户重复购买，不允许多个客户重复购买某商品是不是没意义……我有点脑残。

[lance6716]

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

[letianqiu]

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

[18577347704]

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

[lance6716]

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