葡萄酒交易贪婪解决方案(SPOJ)的形式正确性证明？

Question

不要误会我在网上法官上发布一个问题的问题。我只想知道如何证明解决方案的正确性。以下是问题Wine trading problem。它说，在单位距离内有一排房子，每座房子要么想卖，要么想买酒。总需求=总供给。在一次交易中所做的工作是所涉及的酒量乘以距离。问题是在最小的工作量下满足所有房屋的需求。建议的解决方案是第一个卖家(从行的右边开始)卖给第一个买家(金额=min(卖家，买家))(这是贪婪的选择)，然后解决剩余的问题。如何才能正式证明这一点是正确的？

Answer 1

我不确定它是否像你想要的那样正式，但这里有一个直观的证明。

为了简化起见，我将供应商标记为“+”，其他标记为“-”。

WLOG，我将从左侧的供应商开始。所以你可以选择买家。

+         -    -

假设你没有选择第一个。

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

然后你必须由另一个供应商提供第一个供应商，而你选择他的唯一原因是他离第一个买家更近。他可以在第一个买家的左边或右边。

左边

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

嗯，距离与贪婪的解决方案完全相同。

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

正确的

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

那么，贪婪的解决方案会更好(因为它避免了重叠)。

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

换句话说，贪婪只有在必要的时候才会重叠，如果没有，它会从重叠距离的2倍中受益。