r******e
发帖数: 244 | 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********5
发帖数: 715 | 2 第一题， the sum of the height differences of the n pairs，所有男生的height
的总和和所有女生的height的总和难道不是不变的么？如果是不变的话那么height
difference不是也不变了？或者题目的意思是男生可以和男生pair，女生可以和女生
pair？ |
r*******e
发帖数: 7583 | 3 sum of diff != |sum of male - sum of female|
sum of diff = |diff1| + |diff2| ... + |diffn|
height
【在 M********5 的大作中提到】
: 第一题， the sum of the height differences of the n pairs，所有男生的height
: 的总和和所有女生的height的总和难道不是不变的么？如果是不变的话那么height
: difference不是也不变了？或者题目的意思是男生可以和男生pair，女生可以和女生
: pair？
|
M********5
发帖数: 715 | 4 想错了，我以为不用加绝对值。。。
【在 r*******e 的大作中提到】
: sum of diff != |sum of male - sum of female|
: sum of diff = |diff1| + |diff2| ... + |diffn|
:
: height
|
r**h
发帖数: 1288 | 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*****u
发帖数: 648 | 6 第一题，关于greedy解法，貌似大家轮流挑，每个人都挑目前pool里剩下于自己身高最
近的异性就行了吧。先男女分别排个序，挑起来更快.
证明每轮挑的人没有motivation舍近求远就行了 （反正你多差一寸别人顶多也就少差
一寸） |
r*******e
发帖数: 7583 | 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*****y
发帖数: 1071 | 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*******e
发帖数: 7583 | 9 是的
我举的例子是按楼上的greedy挑法选的
【在 j*****y 的大作中提到】
: 这个难道不是 3-1, 4-2, 5-6 ?
|
j*****y
发帖数: 1071 | 10 感觉就应该是对 n个 male的身高排序， 对 n个 female的身高排序。
然后对应的配对就行了吧？
【在 r*******e 的大作中提到】
: 是的
: 我举的例子是按楼上的greedy挑法选的
|
|
|
M********5
发帖数: 715 | 11 我也感觉是不是这样，但是可以证明吗？
【在 j*****y 的大作中提到】
: 感觉就应该是对 n个 male的身高排序， 对 n个 female的身高排序。
: 然后对应的配对就行了吧？
|
l****i
发帖数: 2772 | 12 先把所有男女差为0的配对，再把所有男女差为1的配对，直到全部配对完。这样复杂度
是多少？O（N^3）？ |
S******t
发帖数: 151 | 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*****y
发帖数: 1071 | 14 你先看两个男的，两个女的吧， 排序后， 为了证明的方便，可以假设
男的身高是
0 x, x >= 0
女的身高是
y y+e, e>=0
需要证明 |y| + |y + e - x| <= |y - x| + |y + e|
这个证明不难，我刚才试了一下。
【在 M********5 的大作中提到】
: 我也感觉是不是这样，但是可以证明吗？
|
f*****e
发帖数: 2992 | 15 可以证明啊:
假如最优的有两对(M1,W1), (M2,W2)，顺序不一样：
M1 < M2
W1 > W2
则我们可以通过交换
(M1,W2)，(M2,W1)来得到至少一样优的结果。
【在 M********5 的大作中提到】
: 我也感觉是不是这样，但是可以证明吗？
|
r*******e
发帖数: 7583 | 16 是的，俺想复杂了
【在 S******t 的大作中提到】
: 直接对男女身高排序，然后直接按序匹配即可，复杂度O(nlogn)。
: 这题用最优权匹配当然是可以做，只不过没有利用问题的性质罢了。
|
S******t
发帖数: 151 | 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*****y
发帖数: 1071 | 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******t
发帖数: 151 | 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*****y
发帖数: 1071 | 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*****y
发帖数: 1071 | 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*****u
发帖数: 648 | 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****g
发帖数: 1 | 23 assignment problem. use modified shortest path search in bipartite graph |
f******t
发帖数: 18 | 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******t
发帖数: 18 | 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******e
发帖数: 244 | 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******e
发帖数: 244 | 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******e
发帖数: 244 | 28 感觉不是这样的
【在 l****i 的大作中提到】
: 先把所有男女差为0的配对，再把所有男女差为1的配对，直到全部配对完。这样复杂度
: 是多少？O（N^3）？
|
c*****a
发帖数: 808 | 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******e
发帖数: 244 | 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*****a
发帖数: 808 | 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;i
dp[i][0]=INTMAX;
for(int i =1;i
dp[0][i]=INTMAX;
dp[0][0]=0;
for(int i =1;i
for(int j=1;j
dp[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********r
发帖数: 286 | 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******e
发帖数: 244 | 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;
|
