Fibonacci and Lucas Numbers with Applications, Volume 1, 2nd Edition

THE KNAPSACK PROBLEM

In this chapter, we investigate the well-known knapsack problem, with Fibonacci and Lucas numbers as weights.

Let denote the th gibonacci number. Recall from Chapter 7 that

Consequently,

28.1

We will use this result in our discussion.

28.1 THE KNAPSACK PROBLEM

Given a knapsack of integer volume , and n items of integer volumes , which of the items can fill the knapsack?

In other words, given the positive integers , called weights, and a positive integer , solve the linear diophantine equation (LDE) , where or 1. This is the well-known knapsack problem.

In particular, ...