Формальное подтверждение правильности решения Greedy для торговли вином (SPOJ)?

Question

Не поймите меня неправильно, если вы разместите вопрос о проблеме на онлайн-судье. Я просто хочу знать, как доказать правильность решения. Следующая проблема - проблема торговли вином. Там написано, что на расстоянии в единицу стоит ряд домов, и каждый хочет продать или купить вино. Общий спрос = общее предложение. Работа, проделанная в сделке, - это количество вина, умноженное на расстояние. Проблема состоит в том, чтобы удовлетворить потребность всех домов в минимальных работах. Предлагаемое решение состоит в том, что первый продавец (скажем, начиная с правой стороны строки) продает первому покупателю (сумма = мин. (Продавец, покупатель))(это жадный выбор), а затем решает оставшуюся проблему. Как можно формально доказать, что это правильно?

Answer 1

Не уверен, что это так формально, как вы хотите, но вот интуиция доказательства.

Для упрощения отмечу поставщиков как "+", а других как "-".

WLOG, я начну с поставщика на левой стороне. Так что у вас есть выбор покупателя.

+         -    -

Предположим, вы не выбрали первый.

+         -    -
<==============>

Затем вы должны накормить первого поставщика другим поставщиком, и единственная причина, по которой вы могли бы выбрать его, заключается в том, что он ближе к первому покупателю. Он может быть слева или справа от первого покупателя.

ОСТАВИЛ

+      +  -    -
<==============>
       <==>

Ну, расстояние точно такое же, как и у жадного решения.

+      +  -    -
<=========>
       <=======>

ПРАВО

+         - +  -
<==============>
          <=>

Ну, жадное решение было бы лучше (так как оно избегает дублирования).

+         - +  -
<=========>
            <==>

Другими словами, жадность перекрывается только тогда, когда это необходимо, а если нет, то она выигрывает в 2 раза от расстояния перекрытия.