d*****r
发帖数: 57 | 1 【 以下文字转载自 CS 讨论区 】
发信人: driftor (信天游), 信区: CS
标 题: Google 电面 algorithm 问题
发信站: BBS 未名空间站 (Mon Mar 29 00:02:17 2010, 美东)
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.)
感觉应该是很基本的问题，可惜本人背景太弱，望不吝赐教，多谢！ |
x***y
发帖数: 633 | 2 Job assignment(or node matching) problem. Usually, greedy algorithm can get
an approximation result. However, this has one exact polynomial solution: Hungarian Method, which is not simple and impossbile to get in the interview if you never meet it before.... |
r****o
发帖数: 1950 | 3 实在不行遍历bidder的所有permutation，找出最优解可否？ |
d**e
发帖数: 6098 | 4 max flow problem?
具体怎么算也忘了，书看得还是不够
get
Hungarian Method, which is not simple and impossbile to get in the interview
if you never meet it before....
【在 x***y 的大作中提到】
: Job assignment(or node matching) problem. Usually, greedy algorithm can get
: an approximation result. However, this has one exact polynomial solution: Hungarian Method, which is not simple and impossbile to get in the interview if you never meet it before....
|
S*******w
发帖数: 24236 | 5 assignment problem
interview
【在 d**e 的大作中提到】
: max flow problem?
: 具体怎么算也忘了，书看得还是不够
:
: get
: Hungarian Method, which is not simple and impossbile to get in the interview
: if you never meet it before....
|
x*******u
发帖数: 2074 | 6 加一个super source和一个super sink就可以
interview
【在 d**e 的大作中提到】
: max flow problem?
: 具体怎么算也忘了，书看得还是不够
:
: get
: Hungarian Method, which is not simple and impossbile to get in the interview
: if you never meet it before....
|
d**e
发帖数: 6098 | 7 google了一下，和 max flow 差不多的问题
【在 S*******w 的大作中提到】
: assignment problem
:
: interview
|
d**e
发帖数: 6098 | 8 对……
【在 x*******u 的大作中提到】
: 加一个super source和一个super sink就可以
:
: interview
|
x****r
发帖数: 99 | 9 maxflow可以解匹配的问题，但是那种情况下每条边都是1， 请问这题怎么解? 怎么用
maxflow来限定每个人只能买一个商品？？比如一个bidder对3个商品分别出价10， 20
， 30， 那super source到这个bidder的边应该设多少capacity?
谢谢。 |
Y*****y
发帖数: 361 | 10 如果要求每个人最多分一个东西，那么就是一个maximum weighted bipartite
matching问题。Hungarian algorithm以
及后来派生出来的算法都可以解。
但是看楼主的描述，好像没有限制每个人最多分几个东西，也没有限制最多花多少钱。
那这个问题应该就很简单了。对每个
产品，scan一遍所有人的bid，谁最高就分给谁。O(n^2)的时间复杂度。
【在 d*****r 的大作中提到】
: 【 以下文字转载自 CS 讨论区 】
: 发信人: driftor (信天游), 信区: CS
: 标 题: Google 电面 algorithm 问题
: 发信站: BBS 未名空间站 (Mon Mar 29 00:02:17 2010, 美东)
: 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.)
: 感觉应该是很基本的问题，可惜本人背景太弱，望不吝赐教，多谢！
|
h**6
发帖数: 4160 | 11
还是楼上观察仔细啊，赞一个。
多项式时间内匈牙利算法可以解这类任务分配问题而不能解行脚商人问题，原因在于任务分配问题可以有内部小循环。
【在 Y*****y 的大作中提到】
: 如果要求每个人最多分一个东西，那么就是一个maximum weighted bipartite
: matching问题。Hungarian algorithm以
: 及后来派生出来的算法都可以解。
: 但是看楼主的描述，好像没有限制每个人最多分几个东西，也没有限制最多花多少钱。
: 那这个问题应该就很简单了。对每个
: 产品，scan一遍所有人的bid，谁最高就分给谁。O(n^2)的时间复杂度。
|
x****r
发帖数: 99 | 12 如果真的是这样，这个题目就挺没意思的啊。。
【在 Y*****y 的大作中提到】
: 如果要求每个人最多分一个东西，那么就是一个maximum weighted bipartite
: matching问题。Hungarian algorithm以
: 及后来派生出来的算法都可以解。
: 但是看楼主的描述，好像没有限制每个人最多分几个东西，也没有限制最多花多少钱。
: 那这个问题应该就很简单了。对每个
: 产品，scan一遍所有人的bid，谁最高就分给谁。O(n^2)的时间复杂度。
|
r****o
发帖数: 1950 | 13 原题不是说了么?
(Of coz, each merchandise can be sold to one and only one bidder.)
【在 x****r 的大作中提到】
: 如果真的是这样，这个题目就挺没意思的啊。。
|
d*******d
发帖数: 2050 | 14 但没说每个ｂｉｄｄｅｒ只能买一个阿．
【在 r****o 的大作中提到】
: 原题不是说了么?
: (Of coz, each merchandise can be sold to one and only one bidder.)
|
