M*******a
发帖数: 1633 | 1 就是两个vector A(a1, a2, a3....an), B(b1, b2, b3... bn)，a1..an和b1..bn都可
以为负数。
然后可以调整各项a1..an/b1..bn的位置，求A和B乘积A*B = a1*b1 + a2*b2... an*bn
的最大值 |
e********2
发帖数: 495 | 2 Max weight matching, polynomial time complexity
bn
【在 M*******a 的大作中提到】
: 就是两个vector A(a1, a2, a3....an), B(b1, b2, b3... bn)，a1..an和b1..bn都可
: 以为负数。
: 然后可以调整各项a1..an/b1..bn的位置，求A和B乘积A*B = a1*b1 + a2*b2... an*bn
: 的最大值
|
M*******a
发帖数: 1633 | 3 这么神奇？
是更什么bipartite matching一个意思么？
【在 e********2 的大作中提到】
: Max weight matching, polynomial time complexity
:
: bn
|
h*******e
发帖数: 1377 | 4 怎么感觉感觉排序 之后 正数部分大的乘大的，负数 也是最小的乘最小的。。然后中
间乘中间，贪心就行呢 |
l******6
发帖数: 340 | 5 agree
sort(A.begin() , A.end())
sort(B.begin() , B.end())
sum(A[i] * B[i])
【在 h*******e 的大作中提到】
: 怎么感觉感觉排序 之后 正数部分大的乘大的，负数 也是最小的乘最小的。。然后中
: 间乘中间，贪心就行呢
|
M*******a
发帖数: 1633 | 6 好像是找不出反例来
【在 l******6 的大作中提到】
: agree
: sort(A.begin() , A.end())
: sort(B.begin() , B.end())
: sum(A[i] * B[i])
|
l******6
发帖数: 340 | 7 I can think of a proof:
for any A[i] <= A[j] , B[i] <= B[j]
A[i](B[i] - B[j]) >= A[j](B[i] - B[j])
A[i]B[i] + A[j]B[j] >= A[i]B[j] + A[j]B[i]
this hold for every pair in A[] and B[] and we can always optimize a pair
by switch if A[i] <= A[j] and B[i] >= B[j]
lead to the final result to sorted A[] and B[]
【在 M*******a 的大作中提到】
: 好像是找不出反例来
|
M*******a
发帖数: 1633 | 8 哈，有道理
【在 l******6 的大作中提到】
: I can think of a proof:
: for any A[i] <= A[j] , B[i] <= B[j]
: A[i](B[i] - B[j]) >= A[j](B[i] - B[j])
: A[i]B[i] + A[j]B[j] >= A[i]B[j] + A[j]B[i]
: this hold for every pair in A[] and B[] and we can always optimize a pair
: by switch if A[i] <= A[j] and B[i] >= B[j]
: lead to the final result to sorted A[] and B[]
|
z**********u
发帖数: 201 | 9 这个感觉是个两个向量的内积啊，matrix A1的每一列是向量A的a1...an的全排列，所
以矩阵A 共有n！列，列向量b= [b1,..,bn]'，A'*b取其中最大元素应该就是所求的了
所以应该不是多项式时间的 不知道对不对。。。 |
M*******a
发帖数: 1633 | 10 都n!了还能多项式？
【在 z**********u 的大作中提到】
: 这个感觉是个两个向量的内积啊，matrix A1的每一列是向量A的a1...an的全排列，所
: 以矩阵A 共有n！列，列向量b= [b1,..,bn]'，A'*b取其中最大元素应该就是所求的了
: 所以应该不是多项式时间的 不知道对不对。。。
|
z**********u
发帖数: 201 | 11 错了。。。当时光想着做法了。。。晕死
【在 M*******a 的大作中提到】
: 都n!了还能多项式？
:
:
|
b*****t
发帖数: 296 | 12 maxMultiplication(A[n], B[n]) {
return maxMultiplication(A[n-1], b[n-1])+getMaxValue(A)*getMaxValue(B);
} |
m*********a
发帖数: 3299 | 13 这个不就是这个吗
agree
sort(A.begin() , A.end())
sort(B.begin() , B.end())
sum(A[i] * B[i])
【在 b*****t 的大作中提到】
: maxMultiplication(A[n], B[n]) {
: return maxMultiplication(A[n-1], b[n-1])+getMaxValue(A)*getMaxValue(B);
: }
|
