p**********e
发帖数: 316 | 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 | l******6
发帖数: 340 | 2 sort both A and B
Assign number with same idx in A and B into a pair | g*********e
发帖数: 14401 | 3 greedy algorithm
then prove it's optimal | l******6
发帖数: 340 | 4
example
A 2 , 6
B 3 , 0
How greedy works?
【在 g*********e 的大作中提到】
: greedy algorithm
: then prove it's optimal
| g*********e
发帖数: 14401 | 5
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**********e
发帖数: 316 | 6 怎么证明这种解法就是最小呢
【在 l******6 的大作中提到】
: sort both A and B
: Assign number with same idx in A and B into a pair
| c***0
发帖数: 449 | 7 先计算两个数组和的差， 再算算每对数组元素之间的差， 如果有某对的差在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*c
发帖数: 167 | 8 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**8
发帖数: 4527 | 9 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*****0
发帖数: 452 | | h*****u
发帖数: 109 | 11 这是经典的assignment problem.
最早的算法是Kuhn提出的Hungarian algorithm.
也可以用Linear programming来formulate，所以Simplex, Dual Simplex也可以。
最快的方法是Jonker and Volgent的算法，用大量的preprocessing.
从这开始： http://en.wikipedia.org/wiki/Hungarian_algorithm | x****g
发帖数: 1512 | 12 为啥不是
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
|
|
