Courtyard New Haven willingford 附近有什么好的中餐馆可推荐 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PennySaver - 省钱一族

Courtyard New Haven willingford 附近有什么好的中餐馆可推荐

Courtyard New Haven willingford 附近有什么好的中餐馆可推荐# PennySaver - 省钱一族

p*e2010-09-14 07:09

1 楼

there are two groups of people; n number of A's & n of B's. We want to have
n pairs of A and B from two groups and to minimize the sum of the weight
differences.
EG
A[]={5,3,4};
B[]={1,6,2};
min = 5
3-1, 4-2,5-6

S*02010-09-14 07:09

2 楼

rt,还有什么地方可逛的吗，知道的dx请推荐。 thanks!

l*62010-09-14 07:09

3 楼

sort both A and B
Assign number with same idx in A and B into a pair

g*e2010-09-14 07:09

4 楼

greedy algorithm
then prove it's optimal

l*62010-09-14 07:09

5 楼

example
A 2 , 6
B 3 , 0
How greedy works?

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

: greedy algorithm
: then prove it's optimal

g*e2010-09-14 07:09

6 楼

sort A, B then match each pair 6-3, 2-0
given(A1 < A2), (B1 < B2)
cost((A1, B1), (A2, B2)) is always no greater than cost((A1, B2), (A2,B1))

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

:
: example
: A 2 , 6
: B 3 , 0
: How greedy works?

p*e2010-09-14 07:09

7 楼

怎么证明这种解法就是最小呢

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

: sort both A and B
: Assign number with same idx in A and B into a pair

c*02010-09-14 07:09

8 楼

先计算两个数组和的差，再算算每对数组元素之间的差，如果有某对的差在0与和的
差之间，那就找出最接近和的差的一半的那一对，进行对调，然后重新计算新的数组的
差，以此递归，直到找不出任何一对的差在0与和的差之间为止。

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

:
: sort A, B then match each pair 6-3, 2-0
: given(A1 < A2), (B1 < B2)
: cost((A1, B1), (A2, B2)) is always no greater than cost((A1, B2), (A2,B1))

r*c2010-09-14 07:09

9 楼

I tend to believe either Greedy or DP works. Here is a DP solution, not
fully tested. Greedy is preferred, as it is cleaner and shorter.
int minPairDistSum(const vector num1, const vector num2) {
int len = num1.size();
assert(len == num2.size());
if(len <= 0) return INT_MIN;
vector >dp(len + 1, vector(len +1, 0));
for(int i=0; i<=len; ++i){
for(int j=0; j<=len; ++j){
dp[i][j] = INT_MAX;
if(i==j && j==0) continue;
if(i==0) {dp[i][j] = num1[j -1]; continue;}
if(j==0) {dp[i][j] = num2[i -1]; continue;}
if(i != j)
dp[i][j] = num1[j-1] - num2[i-1];
else {
if(i ==1) {
dp[i][j] = num1[i-1]-num2[i-1];
continue;
}
int alt0 = dp[i-1][j-1] + num1[i-1]-num2[i-1];
if(i ==2) {
dp[i][j] = std::min(alt0, dp[i-1][j-1] + dp[i][j-1])
;
continue;
}
int alt1 = dp[i][j-2] + dp[i-2][j-1] + dp[i-1][j];
int alt2 = dp[i-1][j-2] + dp[i][j-1] + dp[i-2][j];
dp[i][j] = std::min(alt0, std::min(alt1, alt2));
}
}
}
return dp[len][len];
}

t*82010-09-14 07:09

10 楼

very easy to confirm

a,b (a < b)
c, d (c < d)
1. enumerate a< c, ...... a > c .....
2 . more simple solution
pointX (a, b), pointY (c, d)
because 0 < a < b and 0 < c < d
pointX and pointY is in range less than 45 degree from the vertical
ASIX, mirror PointY to the 45 scope line. etc. compare
two distance |a -c| + |b -d| pretty easy

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

: 怎么证明这种解法就是最小呢

x*02010-09-14 07:09

11 楼

h*u2010-09-14 07:09

12 楼

这是经典的assignment problem.
最早的算法是Kuhn提出的Hungarian algorithm.
也可以用Linear programming来formulate，所以Simplex, Dual Simplex也可以。
最快的方法是Jonker and Volgent的算法，用大量的preprocessing.
从这开始： http://en.wikipedia.org/wiki/Hungarian_algorithm

x*g2010-09-14 07:09

13 楼

为啥不是
2-3 = -1
4-6 = -2
5-1 = +4
pair不分顺序都是a-b,不能b-a?
min = 1 ?

have

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

: there are two groups of people; n number of A's & n of B's. We want to have
: n pairs of A and B from two groups and to minimize the sum of the weight
: differences.
: EG
: A[]={5,3,4};
: B[]={1,6,2};
: min = 5
: 3-1, 4-2,5-6