贪婪算法的证明

Question

我最近尝试在Codeforce上解决一个问题，我确实得到了正确的解决方案，但现在正在努力证明这一点。算法是这样的：

采取最小的折扣，并将其应用于最昂贵的，并免费使用连续两个较便宜的。然后继续这样做，直到所有的项目都没有了。

我有点卡在证据上了。如果有人能给我一个矛盾的正式证明，那就太好了。

Problem！

Answer 1

它分为两个部分：

选择哪个折扣？

假设我们选择接受最小折扣(n items，n<m)之外的任何其他折扣( m商品免费2个)：购买文章a(1)到a(m)，我们免费获得文章b和c。我们可以只采取最小的折扣，购买文章a(1)到a(n)免费获得b和c，购买商品a(n+1)到a(m)以全价结束同样的情况。因此，选择最小的折扣与其他选择一样是最差的。

选择哪些免费文章？

现在假设我们将折扣应用于商品a1和a2，而不是b1 an b2 (cost(a1)<cost(b1)或cost(a2)<cost(b2))中最贵的商品。让我们假设cost(a1)<cost(a2)是对称的。出现了三种情况：

1. 作为促销活动的一部分，我们仍然设法免费获得了a2：如果我们还没有选择的话，我们也可以获得a1。
2. 我们必须为它付费，作为折扣的一部分。折扣允许我们购买价格高达c的商品。出现了以下情况之一:我们可以交换a1和a2，这导致此篮子的成本更低，而不更改任何东西，让我们称之为d和e我们从这个第二个折扣中获得的项目，d是最昂贵的一个。我们可以在第一个折扣中选择a2作为免费项目，在第二个折扣中将其替换为d，并在第二个折扣中选择a1作为免费项目，从而产生更低或相等的cost.

​

1. 我们买它是打折的:我们本可以选择a2，然后在不改变任何其他东西的情况下以更低的成本支付a1，因此选择a1是次优的。