algorithm - 贪心算法的证明

Question

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

拿最小的折扣，把它应用到最贵的，连续两个便宜的免费。然后不断地做，直到没有物品剩下。

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

问题！

Answer 1

它分为两部分：

选择哪个折扣？

假设我们选择m除最小的折扣（n物品， ）之外的任何其他折扣（物品免费 2 n<m）：购买物品a(1)我们免费a(m)获得b物品c。我们可以采取最小的折扣，购买物品a(1)以免费a(n)获得，b并以全价购买物品最终处于相同的情况。因此，选择最小的折扣在最坏的情况下与其他选择相提并论。ca(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和支付，因此挑选不是最理想的。a1a1