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