The key observation to this problem is that a Fibonacci number is equal to the two before it: hence, instead of taking an item, you can take the two listed before it. Since you can only take ~1~ of each item, there are only ~\frac k 2~ combinations of Fibonacci numbers to try. There are some tricky edge cases in this problem: If ~k>n+1~, then it is guaranteed to be impossible. In addition, since the first two items have equal masses of ~1~, whenever you would take the ~2~nd item, you can also take the first item.

Time Complexity: ~\mathcal{O}(N)~