Задача о минимуме/максимуме скалярного произведения
| Задача: |
| Необходимо найти минимальную/максимальную суммы попарных произведений для двух заданных упорядоченных наборов чисел. |
Решение
Скалярным произведением двух упорядоченных последовательностей чисел будем называть число
| Теорема (о минимуме/максимуме скалярного произведениях[1]): |
Минимум скалярного произведения достигается при сопоставлении возрастающей последовательности и убывающей последовательности . При сопоставлении возрастающей достигается максимум. |
| Доказательство: |
| Будем считать, что последовательность отсортирована по возрастанию. Покажем, что если существуют пары чисел и , такие что и , то скалярное произведение можно уменьшить, поменяв местами и . Так как в нашем случае , то , а следовательно данное скалярное произведение не является минимальным. Проделав такую замену для всех получим отсортированную по убыванию последовательность , и скалярное произведение такой пары последовательностей будет минимальным. Аналогично для получения максимума во всех парах чисел и , таких что и нужно менять местами и . В результате получится отсортированная по возрастанию последовательность, и скалярное произведение в таком случае будет максимальным. |
Данная теорема нашла себе практическое применение в теории матроидов и расписаний.
Примечания
См. также
Источники информации
- Романовский И. В. Дискретный анализ. — 3-е изд. — С. 320 — ISBN 5-7940-0114-3.
