Обратите внимание, что эту проблему иногда называют проблемой лыж и лыжников, когда у вас есть n лыж и m лыжников различной длины и высоты. Цель состоит в том, чтобы сопоставить лыжи с лыжниками так, чтобы сумма различий между высотой и длиной лыж сводилась к минимуму.
Чтобы решить эту проблему, вы можете использовать двустороннее сопоставление минимального веса, которое требует времени O (n ^ 3).
Еще лучше, вы можете достичь O (n ^ 2) времени с O (n) дополнительной памятью, используя простой алгоритм динамического программирования ниже.
Оптимально, вы можете решить проблему за линейное время, если точки уже отсортированы, используя алгоритм, описанный в этой статье .
O (n ^ 2) алгоритм динамического программирования:
if (size(B) > size(A))
swap(A, B);
sort(A);
sort(B);
opt = array(size(B));
nopt = array(size(B));
for (i = 0; i < size(B); i++)
opt[i] = abs(A[0] - B[i]);
for (i = 1; i < size(A); i++) {
fill(nopt, infinity);
for (j = 1; j < size(B); j++) {
nopt[j] = min(nopt[j - 1], opt[j - 1] + abs(A[i] - B[j]));
swap(opt, nopt);
}
return opt[size(B) - 1];
После каждой итерации i внешнего цикла for, указанного выше, opt[j] содержит оптимальное решение, соответствующее {A[0],..., A[i]} с использованием элементов {B[0],..., B[j]}.
Правильность этого алгоритма основывается на том факте, что при любом оптимальном сопоставлении, если a1 сопоставляется с b1, a2 сопоставляется с b2 и a1