algorithm - 贪心算法的证明

Question

我最近尝试在 Codeforces 上解决一个问题，我确实得到了正确的解决方案，但现在正试图证明它。算法是这样的:

取最小的折扣并应用在最贵的上，并免费使用连续两个较便宜的。然后不断重复，直到没有剩余元素为止。

我有点卡在证明上了。如果有人能给我一个正式的反证法就好了。

Problem !

Answer 1

分为两部分:

选择哪个折扣？

假设我们选择除最小折扣(m 件，n )之外的任何其他折扣(n<m 件免费 2 件):购买商品 a(1)至 a(m)我们得到文章b和 c免费。我们可以拿最小的折扣，买文章a(1)至 a(n)得到b和 c免费，购买元素a(n+1)至 a(m)全价以同样的情况结束。因此，选择最小折扣最多只能与其他选择相提并论。

挑选哪些免费文章？

现在假设我们将折扣应用于商品 a1和 a2而不是最昂贵的b1一个b2 ( cost(a1)<cost(b1) 或 cost(a2)<cost(b2) )。让我们假设 cost(a1)<cost(a2)因为案例是对称的。出现三种情况:

1. 不知何故我们仍然设法得到 a2免费作为促销的一部分:那么我们也可以获得 a1如果我们还没有选择它的话。
2. 作为折扣的一部分，我们必须为此付费。折扣使我们能够购买成本高达 c 的商品.出现以下情况之一:
   • c<=cost(a1) : 我们可以交换 a1和 a2 ，这会导致此篮子的成本降低，而无需更改任何其他内容。
   • cost(a2)<=c<cost(a1) :让我们调用d和 e我们从第二次折扣中得到的元素，d是最贵的。我们本可以选择 a2作为第一次折扣中的免费项目，将其替换为d在第二个和采摘a1作为第二次折扣中的免费项目，导致成本更低或相同。
3. 我们以折扣价购买它:我们可以选择 a2并支付了a1为了在不改变任何其他东西的情况下降低成本，因此选择 a1是次优的。