0

Задача такая - дано положительное число n, целые числа в порядке возрастания p1 < p2 < ... < pk, и c1, c2, ..., ck. pi - координаты точек на оси, ci - их веса. Нужно выбрать точки так, чтобы сумма их весов была максимальной, но расстояние между любой парой точек была не меньше n.

Я догадываюсь, что задача решается с помощью динамического программирования, но возникла сложность с алгоритмом - как, зная набор из k-1 точек с максимальным весом, найти набор для k?

4
  • 1
    Динамика вперёд: F[i] - максимальная сумма, если взять текущую точку. Начальное состояние - F[i] = a_i Пересчёт - F[j] = max { F[k] + | p_k <= p_j - n } + a_j. Ответ - максимум по всем F Сложность если не совсем в лоб то линейная.
    – pavel
    23 фев 2016 в 14:58
  • @pavel, что значит "| p_k <= p_j - n"?
    – Parket
    23 фев 2016 в 16:15
  • таких что расстояние между ними больше n.
    – pavel
    23 фев 2016 в 18:44
  • тогда знак "+" лишний?
    – Parket
    23 фев 2016 в 19:32

1 ответ 1

1

Эта задача динамического программирования нелинейна. Оптимальное решение для k точек в общем случае не содержит оптимального набора для k-1 точек.

Но если говорить о множестве всех возможных наборов для данного k, то при отбрасывании любой его точки каждый получаемый набор с очевидностью является допустимым для k-1. Но это - совсем другая сложность алгоритма.

Поставленная задача - типичная "задача о рюкзаке", на сайте есть разбор. Возникнут конкретные проблемы - будем разбираться.

3
  • А как тогда, хотя бы примерно, составить алгоритм этой задачи?
    – Parket
    23 фев 2016 в 18:33
  • @Parket Добавил ссылку. 23 фев 2016 в 21:42
  • Проблемы все-таки возникли ru.stackoverflow.com/questions/497796/…
    – Parket
    27 фев 2016 в 19:32

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.