d*****r 发帖数: 57 | 1 N bidders bid on N merchandises. Each bidder provides a bidding price on
every of the N merchandises, P(i,j). How to allocate the merchandises to
each the bidder to maximize the revenue? (Of coz, each merchandise can be
sold to one and only one bidder.)
感觉应该是很基本的问题,可惜本人背景太弱,望不吝赐教,多谢! | a****9 发帖数: 418 | 2 maximum weighted bipartite matching
【在 d*****r 的大作中提到】 : N bidders bid on N merchandises. Each bidder provides a bidding price on : every of the N merchandises, P(i,j). How to allocate the merchandises to : each the bidder to maximize the revenue? (Of coz, each merchandise can be : sold to one and only one bidder.) : 感觉应该是很基本的问题,可惜本人背景太弱,望不吝赐教,多谢!
| j****a 发帖数: 1277 | 3 max-flow-min-cut
【在 d*****r 的大作中提到】 : N bidders bid on N merchandises. Each bidder provides a bidding price on : every of the N merchandises, P(i,j). How to allocate the merchandises to : each the bidder to maximize the revenue? (Of coz, each merchandise can be : sold to one and only one bidder.) : 感觉应该是很基本的问题,可惜本人背景太弱,望不吝赐教,多谢!
| l******e 发帖数: 470 | 4 不好使
【在 j****a 的大作中提到】 : max-flow-min-cut
| b**********g 发帖数: 90 | 5 这个问题问得够刁的,
要是只看你的思路的话,还好.
否则还是很难回答的.
是 maximum weighted matching problem
在 bipartite graph 里稍微要容易点.
http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Maximum_matchings_in_bipartite_graphs
【在 d*****r 的大作中提到】 : N bidders bid on N merchandises. Each bidder provides a bidding price on : every of the N merchandises, P(i,j). How to allocate the merchandises to : each the bidder to maximize the revenue? (Of coz, each merchandise can be : sold to one and only one bidder.) : 感觉应该是很基本的问题,可惜本人背景太弱,望不吝赐教,多谢!
| s**9 发帖数: 207 | 6 How about a greedy algorithm? Output the greatest Pij, then delete row i and
column j; repeat for N times.
Proof that Pij is in one optimal solution: suppose there is an optimal
solution that doesn't include Pij. Then in the solution, bidder i is
assigned with an item k where Pik<=Pij. If Pik is replaced with Pij, the
solution is still optimal if Pij=Pik or is better than the original one if
Pij>Pik. Therefore, Pij must be included in a optimal solution.
【在 d*****r 的大作中提到】 : N bidders bid on N merchandises. Each bidder provides a bidding price on : every of the N merchandises, P(i,j). How to allocate the merchandises to : each the bidder to maximize the revenue? (Of coz, each merchandise can be : sold to one and only one bidder.) : 感觉应该是很基本的问题,可惜本人背景太弱,望不吝赐教,多谢!
| b******t 发帖数: 965 | 7 1 9
9 10
1+10<9+9
and
【在 s**9 的大作中提到】 : How about a greedy algorithm? Output the greatest Pij, then delete row i and : column j; repeat for N times. : Proof that Pij is in one optimal solution: suppose there is an optimal : solution that doesn't include Pij. Then in the solution, bidder i is : assigned with an item k where Pik<=Pij. If Pik is replaced with Pij, the : solution is still optimal if Pij=Pik or is better than the original one if : Pij>Pik. Therefore, Pij must be included in a optimal solution.
|
|