Two problems about Algorithm - 未名空间MITBBS历史存档

Two problems about Algorithm# JobHunting - 待字闺中

r*e2013-03-21 07:03

1 楼

1 In a dance class, n male students and n female students should be paired
so as to minimize the sum of the height differences of the n pairs. Design a
greedy algorithm and a DP algorithm to solve it.
第一题应该是差的绝对值之和吧
2 There are n white dots and n black dots, equally spaced, in a line. You
want to connect each white dot with some one black dot, with a minimum total
length of 'wire'. Design a greedy algorithm and a DP algorithm to solve it.
It is better to have a proof if you use a greedy algorithm.
这两道题目的愿意是，给出greedy的方法，并且证明合理，如果不合理就举出反例。然
后给出DP的方法。

M*52013-03-21 07:03

2 楼

第一题， the sum of the height differences of the n pairs，所有男生的height
的总和和所有女生的height的总和难道不是不变的么？如果是不变的话那么height
difference不是也不变了？或者题目的意思是男生可以和男生pair，女生可以和女生
pair？

r*e2013-03-21 07:03

3 楼

: 第一题， the sum of the height differences of the n pairs，所有男生的height
: 的总和和所有女生的height的总和难道不是不变的么？如果是不变的话那么height
: difference不是也不变了？或者题目的意思是男生可以和男生pair，女生可以和女生
: pair？

M*52013-03-21 07:03

4 楼

想错了，我以为不用加绝对值。。。

【在 r*******e 的大作中提到】

r*h2013-03-21 07:03

5 楼

第一题应该是差的绝对值之和吧
比如说两个组的高度是5 3/4 4，且两个pair是(5,4）（3,4）那么差的和应该是2而不
是0

height

【在 M********5 的大作中提到】

: 第一题， the sum of the height differences of the n pairs，所有男生的height
: 的总和和所有女生的height的总和难道不是不变的么？如果是不变的话那么height
: difference不是也不变了？或者题目的意思是男生可以和男生pair，女生可以和女生
: pair？

b*u2013-03-21 07:03

6 楼

第一题，关于greedy解法，貌似大家轮流挑，每个人都挑目前pool里剩下于自己身高最
近的异性就行了吧。先男女分别排个序，挑起来更快.
证明每轮挑的人没有motivation舍近求远就行了（反正你多差一寸别人顶多也就少差
一寸）

r*e2013-03-21 07:03

7 楼

你这个明显不对
比如男 3 4 5
女 1 2 6
按你的挑法，假定总是男的挑，3-2， 4-6， 5-1，差是7
就算男女轮流挑也不对，随便换个例子就知道了
这个问题应该是min weight matching of bipartite graph
最常见的解法是Hungarian algorithm，复杂度O(n^3)
http://en.wikipedia.org/wiki/Hungarian_algorithm
greedy如果只要O(n^2)，肯定是不对的。。

【在 b*****u 的大作中提到】

: 第一题，关于greedy解法，貌似大家轮流挑，每个人都挑目前pool里剩下于自己身高最
: 近的异性就行了吧。先男女分别排个序，挑起来更快.
: 证明每轮挑的人没有motivation舍近求远就行了（反正你多差一寸别人顶多也就少差
: 一寸）

j*y2013-03-21 07:03

8 楼

这个难道不是 3-1, 4-2, 5-6 ?

【在 r*******e 的大作中提到】

: 你这个明显不对
: 比如男 3 4 5
: 女 1 2 6
: 按你的挑法，假定总是男的挑，3-2， 4-6， 5-1，差是7
: 就算男女轮流挑也不对，随便换个例子就知道了
: 这个问题应该是min weight matching of bipartite graph
: 最常见的解法是Hungarian algorithm，复杂度O(n^3)
: http://en.wikipedia.org/wiki/Hungarian_algorithm
: greedy如果只要O(n^2)，肯定是不对的。。

r*e2013-03-21 07:03

9 楼

是的
我举的例子是按楼上的greedy挑法选的

【在 j*****y 的大作中提到】

: 这个难道不是 3-1, 4-2, 5-6 ?

j*y2013-03-21 07:03

10 楼

感觉就应该是对 n个 male的身高排序，对 n个 female的身高排序。
然后对应的配对就行了吧？

【在 r*******e 的大作中提到】

: 是的
: 我举的例子是按楼上的greedy挑法选的

M*52013-03-21 07:03

11 楼

我也感觉是不是这样，但是可以证明吗？

【在 j*****y 的大作中提到】

: 感觉就应该是对 n个 male的身高排序，对 n个 female的身高排序。
: 然后对应的配对就行了吧？

l*i2013-03-21 07:03

12 楼

先把所有男女差为0的配对，再把所有男女差为1的配对，直到全部配对完。这样复杂度
是多少？O（N^3）？

S*t2013-03-21 07:03

13 楼

直接对男女身高排序，然后直接按序匹配即可，复杂度O(nlogn)。
这题用最优权匹配当然是可以做，只不过没有利用问题的性质罢了。

【在 r*******e 的大作中提到】

: 你这个明显不对
: 比如男 3 4 5
: 女 1 2 6
: 按你的挑法，假定总是男的挑，3-2， 4-6， 5-1，差是7
: 就算男女轮流挑也不对，随便换个例子就知道了
: 这个问题应该是min weight matching of bipartite graph
: 最常见的解法是Hungarian algorithm，复杂度O(n^3)
: http://en.wikipedia.org/wiki/Hungarian_algorithm
: greedy如果只要O(n^2)，肯定是不对的。。

j*y2013-03-21 07:03

14 楼

你先看两个男的，两个女的吧，排序后，为了证明的方便，可以假设
男的身高是
0 x, x >= 0
女的身高是
y y+e, e>=0
需要证明 |y| + |y + e - x| <= |y - x| + |y + e|
这个证明不难，我刚才试了一下。

【在 M********5 的大作中提到】

: 我也感觉是不是这样，但是可以证明吗？

f*e2013-03-21 07:03

15 楼

可以证明啊:
假如最优的有两对(M1,W1), (M2,W2)，顺序不一样：
M1 < M2
W1 > W2
则我们可以通过交换
(M1,W2)，(M2,W1)来得到至少一样优的结果。

【在 M********5 的大作中提到】

: 我也感觉是不是这样，但是可以证明吗？

r*e2013-03-21 07:03

16 楼

是的，俺想复杂了

【在 S******t 的大作中提到】

: 直接对男女身高排序，然后直接按序匹配即可，复杂度O(nlogn)。
: 这题用最优权匹配当然是可以做，只不过没有利用问题的性质罢了。

S*t2013-03-21 07:03

17 楼

顺便说一句，当男生的数量和女生的数量不同的话就需要先排序后DP了。

a
total
it.

【在 r******e 的大作中提到】

: 1 In a dance class, n male students and n female students should be paired
: so as to minimize the sum of the height differences of the n pairs. Design a
: greedy algorithm and a DP algorithm to solve it.
: 第一题应该是差的绝对值之和吧
: 2 There are n white dots and n black dots, equally spaced, in a line. You
: want to connect each white dot with some one black dot, with a minimum total
: length of 'wire'. Design a greedy algorithm and a DP algorithm to solve it.
: It is better to have a proof if you use a greedy algorithm.
: 这两道题目的愿意是，给出greedy的方法，并且证明合理，如果不合理就举出反例。然
: 后给出DP的方法。

j*y2013-03-21 07:03

18 楼

感觉还是用 greedy 就行了吧？
比如男的有 3个，女的有 5个，肯定只能配3对
那么排序后设男的身高是
m1 m2 m3
女的身高是
w1 w2 w3 w4 w5
那么m3选谁呢，只能选 w3, w4, w5中和 m3 最接近的

【在 S******t 的大作中提到】

: 顺便说一句，当男生的数量和女生的数量不同的话就需要先排序后DP了。
:
: a
: total
: it.

S*t2013-03-21 07:03

19 楼

不是的
这个时候光说m1就不一定和w1配对了。
比如
m = {100, 200, 300}
w = {1, 100, 200, 300, 400}

【在 j*****y 的大作中提到】

: 感觉还是用 greedy 就行了吧？
: 比如男的有 3个，女的有 5个，肯定只能配3对
: 那么排序后设男的身高是
: m1 m2 m3
: 女的身高是
: w1 w2 w3 w4 w5
: 那么m3选谁呢，只能选 w3, w4, w5中和 m3 最接近的

j*y2013-03-21 07:03

20 楼

想了一下，我的那个算法不对
看来只能用 dp
比如男的
2 2
女的
0 0 2 3
最优的配对是 2-2, 2-3
但是 greedy 得不到这个

【在 S******t 的大作中提到】

: 不是的
: 这个时候光说m1就不一定和w1配对了。
: 比如
: m = {100, 200, 300}
: w = {1, 100, 200, 300, 400}

j*y2013-03-21 07:03

21 楼

用 dp的话应该是
dp[i][j] 表示前 i个男的和前 j个女的配对产生的身高差距的和的最小值.
dp[i][j] = min(dp[i -1][j -1] + |m[i] - w[j]|, dp[i - 1][j], dp[i][j - 1])

【在 j*****y 的大作中提到】

: 想了一下，我的那个算法不对
: 看来只能用 dp
: 比如男的
: 2 2
: 女的
: 0 0 2 3
: 最优的配对是 2-2, 2-3
: 但是 greedy 得不到这个

b*u2013-03-21 07:03

22 楼

这个反例找的好，我想错了

【在 r*******e 的大作中提到】

: 你这个明显不对
: 比如男 3 4 5
: 女 1 2 6
: 按你的挑法，假定总是男的挑，3-2， 4-6， 5-1，差是7
: 就算男女轮流挑也不对，随便换个例子就知道了
: 这个问题应该是min weight matching of bipartite graph
: 最常见的解法是Hungarian algorithm，复杂度O(n^3)
: http://en.wikipedia.org/wiki/Hungarian_algorithm
: greedy如果只要O(n^2)，肯定是不对的。。

e*g2013-03-21 07:03

23 楼

assignment problem. use modified shortest path search in bipartite graph

f*t2013-03-21 07:03

24 楼

分别给两个身高数组a,b排序，然后按高度顺序匹配就好了~证明大概这样：
假设最优解a[0]不是跟b[0]匹配，那假设是跟b[i](i!=0)，这时候b[0]跟某个a[j](j!=
0)匹配(假设a[0]>=b[0])
只要证明 a[0]-b[0]+|a[i]-b[j]| <= a[0]-b[j]+|a[i]-b[0]|
分三种情况证明：
1.a[i]>=b[0]>=b[j]
2.b[j]<=a[i]3.a[i]把绝对值符号去掉证一下就好了

f*t2013-03-21 07:03

25 楼

忘说了~我假设从大到小排序~

!=

【在 f******t 的大作中提到】

: 分别给两个身高数组a,b排序，然后按高度顺序匹配就好了~证明大概这样：
: 假设最优解a[0]不是跟b[0]匹配，那假设是跟b[i](i!=0)，这时候b[0]跟某个a[j](j!=
: 0)匹配(假设a[0]>=b[0])
: 只要证明 a[0]-b[0]+|a[i]-b[j]| <= a[0]-b[j]+|a[i]-b[0]|
: 分三种情况证明：
: 1.a[i]>=b[0]>=b[j]
: 2.b[j]<=a[i]: 3.a[i]: 把绝对值符号去掉证一下就好了

r*e2013-03-21 07:03

26 楼

我觉得这个方法，应该没错

【在 j*****y 的大作中提到】

: 用 dp的话应该是
: dp[i][j] 表示前 i个男的和前 j个女的配对产生的身高差距的和的最小值.
: dp[i][j] = min(dp[i -1][j -1] + |m[i] - w[j]|, dp[i - 1][j], dp[i][j - 1])

r*e2013-03-21 07:03

27 楼

很有可能，就不能用greedy的方法吧.

【在 r*******e 的大作中提到】

: 你这个明显不对
: 比如男 3 4 5
: 女 1 2 6
: 按你的挑法，假定总是男的挑，3-2， 4-6， 5-1，差是7
: 就算男女轮流挑也不对，随便换个例子就知道了
: 这个问题应该是min weight matching of bipartite graph
: 最常见的解法是Hungarian algorithm，复杂度O(n^3)
: http://en.wikipedia.org/wiki/Hungarian_algorithm
: greedy如果只要O(n^2)，肯定是不对的。。

r*e2013-03-21 07:03

28 楼

感觉不是这样的

【在 l****i 的大作中提到】

: 先把所有男女差为0的配对，再把所有男女差为1的配对，直到全部配对完。这样复杂度
: 是多少？O（N^3）？

c*a2013-03-21 07:03

29 楼

i think for problem 1:
dp[][] = int[a.length+1][b.length+1]
dp[i][j] = abs(a[i-1]-b[j-1]) + min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])

r*e2013-03-21 07:03

30 楼

Is this wrong?
You assume that a[i-1] and b[j-1] are coupled.

【在 c*****a 的大作中提到】

: i think for problem 1:
: dp[][] = int[a.length+1][b.length+1]
: dp[i][j] = abs(a[i-1]-b[j-1]) + min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])

c*a2013-03-21 07:03

31 楼

2个forloop应该把all possible differences刷了吧
大概的code
sort(a);
sort(b);
dp[][] = new int[a.length+1][b.length+1];
dp[0][0]=0;
for(int i =1;idp[i][0]=INTMAX;
for(int i =1;idp[0][i]=INTMAX;
dp[0][0]=0;
for(int i =1;ifor(int j=1;jdp[i][j] = abs(a[i-1]-b[j-1]) + Math.min(dp[i-1][j], dp[i][j-1],
dp[i-1][j-1]);

【在 r******e 的大作中提到】

: Is this wrong?
: You assume that a[i-1] and b[j-1] are coupled.

c*r2013-03-21 07:03

32 楼

咋一看第一题怎么感觉类似best time sell stock ||

a
total
it.

【在 r******e 的大作中提到】

: 1 In a dance class, n male students and n female students should be paired
: so as to minimize the sum of the height differences of the n pairs. Design a
: greedy algorithm and a DP algorithm to solve it.
: 第一题应该是差的绝对值之和吧
: 2 There are n white dots and n black dots, equally spaced, in a line. You
: want to connect each white dot with some one black dot, with a minimum total
: length of 'wire'. Design a greedy algorithm and a DP algorithm to solve it.
: It is better to have a proof if you use a greedy algorithm.
: 这两道题目的愿意是，给出greedy的方法，并且证明合理，如果不合理就举出反例。然
: 后给出DP的方法。

r*e2013-03-21 07:03

33 楼

我的意思是,每一步中不一定加上abs(a[i]-b[j]).
你这样就默认,这种组合.
不应该是这样:
dp[i][j] 表示前 i个男的和前 j个女的配对产生的身高差距的和的最小值.
dp[i][j] = min(dp[i -1][j -1] + |m[i] - w[j]|, dp[i - 1][j], dp[i][j - 1])

【在 c*****a 的大作中提到】

: 2个forloop应该把all possible differences刷了吧
: 大概的code
: sort(a);
: sort(b);
: dp[][] = new int[a.length+1][b.length+1];
: dp[0][0]=0;
: for(int i =1;i: dp[i][0]=INTMAX;
: for(int i =1;i: dp[0][i]=INTMAX;