我最近试着解决一个关于共同力量的问题，我确实得到了正确的解决方案，但现在正试图证明这一点算法如下：
取最小的折扣，并适用于最昂贵的，并采取连续两个较便宜的免费然后继续做，直到没有留下任何东西。
我有点拘泥于证据。如果有人能用矛盾的方式给我一个正式的证明，那就太好了。
Problem！
最佳答案
它分为两部分：
选择哪种折扣？
假设我们选择接受任何其他折扣（对于m商品，2个免费），而不是最小的折扣（n商品，n<m）：购买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)或a2）假设a1，因为情况是对称的。出现三种情况：
不知怎的，作为促销的一部分，我们仍然设法免费获得c：如果我们还没有选择它，那么我们也可以获得c<=cost(a1)。
作为折扣的一部分，我们必须支付。折扣使我们可以购买成本高达a1的商品。出现以下情况之一：a2：我们可以交换cost(a2)<=c<cost(a1)和d，这样可以降低这个篮子的成本，而不需要改变任何其他东西。e：我们打电话给d和a2我们从第二次折扣中得到的商品，d是最贵的。我们可以在第一个折扣中选择a1作为自由项，在第二个折扣中将其替换为a2，在第二个折扣中选择a1作为自由项，从而降低或等于成本。
我们以折扣价购买：我们可以选择a1并支付较低的成本，而不改变任何其他东西，因此选择是次优的。
关于algorithm - 贪婪算法的证明，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14316898/