CODEWITHSUNDEEP
algorithmgreedyproof
gabber12
gabber12

Reputation: 1124

Proof for the greedy algorithm

I recently tried solving a problem on Codeforces I did get the solution right but am now trying to prove it. The algorithm is something like this:

Take the smallest discount and apply it on the most expensive ones and take the two consecutive less expensive ones for free. Then do it continuously till no items are left.

I am kind of stuck on the proof. It would be great if someone can give me a formal proof by contradiction.

Problem!

Upvotes: 1

Views: 465

Answers (1)

Khaur
Khaur

Reputation: 770

It goes in two parts:

Which discount to pick?

Suppose we choose to take any other discount (2 free for m items) than the smallest one (n items, n<m): Buying articles a(1) to a(m) we get articles b and c for free. We could just take the smallest discount, buying articles a(1) to a(n) to get b and c for free, and the buy the items a(n+1) to a(m) for the full price to end up in the same situation. Therefore picking the smallest discount is at worst on par with other choices.

Which free articles to pick?

Now suppose we apply the discount to items a1 and a2 instead of the most expensive ones b1 an b2 (cost(a1)<cost(b1) or cost(a2)<cost(b2)). Let's assume that cost(a1)<cost(a2) since the cases are symmetrical. Three cases arise:

  1. Somehow we still manage to get a2 for free as part of a promotion: then we could also have gotten a1 if we hadn't picked it already.
  2. We have to pay for it, as part of a discount. The discount allows us to buy items costing up to c. One of the following arises:
    • c<=cost(a1): we may swap a1 and a2, which leads to a lower cost for this basket, without changing anything else.
    • cost(a2)<=c<cost(a1): let's call d and e the items we get out of this second discount, d being the most expensive one. We could have picked a2 as a free item in the first discount, replacing it by d in the second and picking a1 as a free item in the second discount, resulting in a lower or equal cost.
  3. We buy it out of a discount: we could have picked a2 and paid a1 for a lower cost without changing anything else, hence picking a1 was suboptimal.

Upvotes: 1

Related Questions