T**e
发帖数: 191 | 1 Suppose you are given a set of n people (with n even) to be seated at a
dinner party. The people will be seated along the two sides of a long table.
o o o o
+------------- ----+
| ... |
+------------- ----+
o o o o
Half are male, half are female. The given function g(p) identifies the
gender of a given person.
As the host, you also know an integer-valued "preference function" h(p1, p2)
for a pair of people p1, p2. The preference function indicates how much the
first person likes the second; it may be negative.
The "score" of a table is determined by the following criteria:
1 point for every adjacent pair (seated next to each other) of people with
one female and the other male.
2 points for every opposite pair (seated across from each other) of people
with one female and the other male.
h(p1, p2) + h(p2, p1) points for every adjacent or opposite pair of people
p1, p2.
Your job as host is to write a search that will find a "good" table score
for a given set of people and preference function.
The data is given to you in the form of an ASCII text file that has the even
number n of people on the first line. The first n/2 people are assumed to
be female, the rest male. The preference matrix follows on the remaining
lines: rows with values separated by spaces. The people are assumed to be
numbered 1..n. The seats are assumed to be numbered such that the top half
of the table has seats 1..n/2 left-to-right, and the bottom half of the
table has seats n/2+1..n left-to-right; thus seat n/2 is opposite seat n.
The output should be a score, then a series of n rows, each with a person
number, then a space, then a seat number. | g****s
发帖数: 340 | 2 这是公司的面试题吗？看起来像算法课的作业。
用DP解。一下子只能想到O(n^5)的。从左到右，依次把每列所有可能pairs的最优total
preference算出来。按照你的图，x为列数(1~n/2)。(pi,pj)代表pi坐在上边，pj坐在
下边。OPT(x,pi,pj)为第x列坐着pi,pj时的preference最大值。那么OPT(0,pi,pj)=0,
OPT(x,pi,pj)=MAX[OPT(x-1,pi',pj') + Preference between (pi',pj') and (pi,pj)] | T**e
发帖数: 191 | 3 偶尔看到的一道算法题，不是面试的。
total
pj)]
【在 g****s 的大作中提到】
: 这是公司的面试题吗？看起来像算法课的作业。
: 用DP解。一下子只能想到O(n^5)的。从左到右，依次把每列所有可能pairs的最优total
: preference算出来。按照你的图，x为列数(1~n/2)。(pi,pj)代表pi坐在上边，pj坐在
: 下边。OPT(x,pi,pj)为第x列坐着pi,pj时的preference最大值。那么OPT(0,pi,pj)=0,
: OPT(x,pi,pj)=MAX[OPT(x-1,pi',pj') + Preference between (pi',pj') and (pi,pj)]
|
|
