[code deleted]

Edited by moderator 29.01.2022 19:44

The short explanation is that the greedy algorithm is wrong.   A simple example: it always places the largest and 2nd largest stones in different piles.   Understanding this, it's not hard to come up with input that fails, e.g.,:
5
4 6 6 7 9
(sum of the largest and next largest stones = sum of remaining smaller stones)

Optimization problems like this generally require that all combinations be examined.  Either in brute force generate and test, or smarter "try all" schemes like recursion with backtracking (and memo-ization) or dynamic programming, to reduce redundant work.

Hello,
Thanks a lot. I was searching for a test case which would fail the greedy algorithm. But still donot understand why the greedy algorithm fails. I am a begineer to algorithms. Could you just explain.

with regards
gogreen.

Hi,

I was using greedy algorithm and found out the flaw. Because there are 2 buckets, and you put one stone after another (this is the major flaw), regardless of its way to keep it minimum difference, there is still a possibility that the combination is not the optimal solution.

For example, I believe that 1,1,1,3 would cause problem. The first step, 1 on bucket1, second step, 1 on bucket2. This equals to the difference to be 0. Third step, 1 on bucket1 or bucket2, fourth step, 3 on opposite of what you did in third step,

However, as you can see the most optimal solution is 1,1,1 in bucket1, 3 in bucket2. Greedy would work if the number of stones on both buckets are equal or have difference of 1 (due to odd numbers).

Edited by author 22.05.2013 07:30