programbhavan's blog

why greedy works with coin change using Fibonacci terms?
By programbhavan, history, 6 years ago, In English

I am recently doing Minimum Fibonacci terms with sum equal to K. i have done using dp approach but tle. but why this problem works with greedy approach.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

According to Zeckendorf's theorem any number can be uniquely described as a sum of Fibonacci numbers.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    so,this unique representation comes from greedy approach ?

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I would like to say, that it isn't unique, unless you mention that the representation is such that no two consecutive fibonacci numbers ( Say $$$F_{n-1}$$$ and $$$F_{n}$$$ ) are used for the representation, because you can just use $$$F_{n+1}$$$ instead.

    → Reply
»
6 years ago, # |
  Vote: I like it +59 Vote: I do not like it

There is an optimal solution that uses each Fibonacci number at most once and never uses two consecutive Fibonacci numbers.

Proof: Take the lexicographically largest solution. It cannot use two consecutive numbers because such a solution would not be optimal (instead of F_n and F_{n+1} take just F_{n+2}). It cannot use 1 twice because using 2 once is better. It cannot use any bigger Fibonacci number twice because instead of F_n + F_n you can have F_{n+1} + F_{n-2} which gives you a lexicographically bigger solution with the same number of coins.

Each number has exactly one representation that uses each Fibonacci number at most once and never uses two consecutive Fibonacci numbers. The greedy algorithm constructs this representation and therefore its output is always optimal.

→ Reply