由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
CS版 - Google 电面 algorithm 问题
相关主题
About the optimal algorithms on matching[转载] 最好的max-weighted bipartite matching的复杂度是?
How to organize the algorithmRe: [转载] 最好的max-weighted bipartite match
Two interview questions? (转载)[转载] 有搞算法的大侠吗?????问个问题!!!
Algorithm 课程及教材选择疑问 (转载)在线等答案,写信
关于计算机算法杂志关于min-max fairness
问个学术问题,optimizaion问题谁有什么solution吗?
question about google algorithm/architecture (转载)CS Algorithm question
急问一篇paper.CS Algorithm Help
相关话题的讨论汇总
话题: pij话题: bidder话题: pik话题: each
进入CS版参与讨论
1 (共1页)
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.

1 (共1页)
进入CS版参与讨论
相关主题
CS Algorithm Help关于计算机算法杂志
How to speed up dell laptop?问个学术问题,optimizaion问题
[转载] latex questionquestion about google algorithm/architecture (转载)
an algorithm question急问一篇paper.
About the optimal algorithms on matching[转载] 最好的max-weighted bipartite matching的复杂度是?
How to organize the algorithmRe: [转载] 最好的max-weighted bipartite match
Two interview questions? (转载)[转载] 有搞算法的大侠吗?????问个问题!!!
Algorithm 课程及教材选择疑问 (转载)在线等答案,写信
相关话题的讨论汇总
话题: pij话题: bidder话题: pik话题: each