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

Question

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

Answer 1

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

Чтобы упростить, я буду отмечать поставщиков как «+», а остальные - «-».

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

+   - - 

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

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

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

ЛЕВЫЙ

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

Ну, расстояние точно так же, как и с жадным раствором.

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

RIGHT

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

Ну, жадный решение было бы лучше (так как это позволяет избежать дублирующих друг друга).

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

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