Блог пользователя programbhavan

why greedy works with coin change using Fibonacci terms?
Автор programbhavan, история, 6 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    so,this unique representation comes from greedy approach ?

    → Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
6 лет назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

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.

→ Ответить