Fibonacci’s backpack

Tudor Văran
The Startup
Published in
10 min readJul 2, 2019

--

My trusty backpack

Not long ago, I found an interesting interview question. Not interesting in the sense that the problem is very challenging, but interesting in the sense that imposing different constraints changes the whole way the problem needs to be approached.

Hypothetically speaking, you are tasked with buying houses for animals in a pet shop. But…what kind of animals are we talking about? If there are hamsters, small cages with a few, fun, running wheels and tunnels are the best, if we’re talking guinea pigs, they should have more space and they are not so active like the hamsters. The context matters so much when trying to solve a problem.

What’s this article for, exactly? Because I want to challenge you. Because I want you to approach a classical problem from different perspectives. Because I want you to approach this problem in a way you probably haven’t thought of. And because I’m nervous for the time being and need to focus my mind on something else.

Now, enough chit-chat about introductory stuff and let’s focus on the problem in question:

You have a large backpack which has a maximum capacity of N kilograms and unlimited quantities of K objects, to which you know each of their weights. All the objects of the same weight are identical. Print the number of ways you can put objects in your backpack such that it reaches maximum capacity and their order matters.

Example: N = 4, K = 2, objects’ weights=[1,2]

There are 5 ways:

  • 1,1,1,1;
  • 2,1,1;
  • 1,2,1;
  • 1,1,2;
  • 2,2.

The problem looks standard and pretty common. However, when approaching it, any candidate would be tempted to ask a few questions:

How large is K?

How large is N?

How heavy are the objects?

In this article I will try to outline different solutions to different constraints of N,K and the objects. If this problem looks easy to you, I suggest skipping to the last section as you might find some food for thought. The restrictions which apply are the following:

  1. small N, small K, objects are small- so small that a maximum of 8-10 can be taken (N < 100, K < 10, weights ~N/10)
  2. K = 2, weights = [1,2]
  3. medium sized N with small K (10.000 ≤ N ≤ 100.000, K < 10)
  4. very large N, objects are small (N > 1.000.000.000, weights < 100)

SMALL N, K, WEIGHTS

If you didn’t get the hints, this screams backtracking. You would almost never have to implement or think about this solution during an interview as it is inefficient, costly space-time wise and it does not look smart.

What you would do is to have a function called backtrack with your current n and the list of objects already in the backpack as parameters. The C code for this solution looks like this:

int ways;
int v[10];
void backtrack(int n, int position) {
if (n > N || position == 10) {
return;
}
if (n == N) {
ways++;
return;
}
for (int i = 0; i < K; ++i) {
v[position] = objects[i];
backtrack(n + objects[i], position + 1);
v[position] = 0;
}
}

K EQUALS 2, OBJECT WEIGH 1 OR 2 kg

Now this is something you might encounter on a real interview. You would be tempted to implement dynamic programming with knapsack. However, your interviewer wants you to observe if you really need O(N) memory and O(N*K) complexity for this. Of course you don’t.

What is simplified in this case is the way we select the number of each object type. For example, for N=7 and our preference of 2 items of 2 kg, of course we would have 3 items of 1 kg left to fill. This could be a good start for our solution.

We have one more question: for our preference of X objects of 2 kg, and our knowledge that Y is the number of objects which have 1 kg, in how many different ways we can place the items in the backpack? We can focus on choosing the positions of one of the two item types and ignore the other (it will be placed in the free spots).

Let’s say we want to choose X random positions in a set of X+Y items and the order doesn’t matter- if we choose the same X positions twice it shouldn’t count. This sounds like combinations of X taken from X+Y. And there’s a formula for that:

C(n,k) = n! / (k! * (n - k)!

Which in our problem translates to:

C(X+Y,X) = C(X+Y,Y) = (X+Y)! / (X! * Y!)

Good! Now we know how many different ways we can place a certain number of X objects, knowing how many objects we’ve chosen, so the code should look like this:

int ways = 0;
for (int X = 0; X <= N / 2; X++) { //
int Y = N - X * 2;
ways += C(X+Y, X);
}

It looks simple and elegant, but there’s one small problem: what is the combination function’ complexity? Looking at the formula, we need to perform X+Y-1 multiplications every time and this equals N-1 for X=0. The complexity would then be O(N²)- not desired.

But what if we perform the multiplications once, at the beginning, and store the partial product in a special vector and every time we need X! we would just look in a vector?

int part_product[N];
for (int i = 0; i <= N; ++i) {
if (i <= 1) {
part_product[i] = 1;
}
else {
part_product[i] = part_product[i-1] * i;
}
}
void C(int n, int k) {
return part_product[n] / (part_product[n-k] * part_product[k]);
}

In this case, we would have O(N) memory and potentially some problems with the int type when dealing with larger N values than 12 (since 13! > 2⁶⁴). If we were to consider working on large numbers, each operation has a complexity of its own, so the best we can do is O(n*digits²), maybe even O(N * digits * lg2(digits)) complexity.

But this solution is not problematic if you can identify the mistakes! If you were tempted to think the same at first, then you’re looking at the problem from a mathematical perspective.

Then again, there’s always the knapsack method. Knapsack dynamic programming refers to a problem-solving technique which relies on dynamic programming — finding a partial solution of the problem and iterating on that with smaller, less complex problems. But before exploring a solution for this, let’s look first at the next constraints and work from there:

MEDIUM SIZED N WITH SMALL K

There’s no denying dynamic programming has no involvement in this solution. We consider: dp[i] = how many ways we can fill a backpack with i capacity.

dp[i] = sum(dp[i - objects[k]]) for all k in [0, K)

Essentially, when looking for the solution for i, we are interested in the solution if there was an item of each kind missing.

int dp[N] = {0,0,.....}; // set all to zeros
dp[0] = 1; // one way for a 0-sized knapsack => empty set
for (int i = 0; i < N; ++i) {
for (int k = 0; k < K; ++k) {
if (!dp[i]) { // no ways to obtain exactly i kilograms
continue;
}
if (i + objects[k] <= N) {
dp[i + objects[k]] += dp[i]; // adding 1 x k-th object
}
}
} // solution is located in dp[N] at the end

Memory: O(N), Complexity: O(N*K)

Let’s go back to our previous requirement: what if we only had 2 objects, and their weights are 1 and 2? By replacing this in the method presented earlier, we get

dp[i] = dp[i-1] + dp[i-2]

This looks awfully familiar to Fibonacci sequence. Since this is the case, we don’t need to store all the solutions, just the previous two ones.

if (N < 2) {
ways = 1;
}
else {
int a = 1, b = 1, c = 0;
for (int i = 2; i <= N; ++i) {
c = a + b;
a = b;
b = c;
}
}

Memory: O(1), Complexity: O(N)

FIBONACCI’S BACKPACK: VERY LARGE N, SMALL WEIGHTS

Here’s some nice food for thought: what if N is very large, so large that you cannot compute each partial solution? (Ignore programming languages limitations on large numbers)

SPOILER: if you want to solve this on your own, don’t read the content below! Find a solution first, then come back later to read the solution.

The solution

There’s a reason I titled this article “Fibonacci’s backpack”. Fibonacci’s series works really nice with the knapsack problem. In fact, we could look at the knapsack problem as a generalized Fibonacci sequence, one where there is no guarantee that the elements that add up to form the next elements are consecutive previous ones.

This approach of the problem works best when the weights are small. If the elements are small, we don’t have to look too far in the dp vector. Let’s salvage somehow the solutions from the previous section and optimize it to suit these new requirements.

The first problem is the memory, we cannot have O(N) when N > 1.000.000.000, this would translate to > 1GB — a number too big. The weights are small (< 100), so we only need to store the previous 100 solutions and perform our dynamic programming from there. Okay, we solved the problem with the memory, but the complexity persists. O(N) is too bad for large N values, we need something faster.

There’s a solution I’ve been holding back on the variant with Fibonacci’s sequence because I didn’t want to spoil this one: you can compute the n-th Fibonacci term in O(lg2(N)) using matrix multiplication and exponentiation by squaring. I will provide the short story for each of these two requirements then I will come back to the solution.

Matrix multiplication

You might wonder, what do matrices have to do with adding some numbers? Well, we could look at the recursivity of Fibonacci’s sequence using matrices.

( F(k+2) )     ( 1  1 )     ( F(k+1) )
( ) = ( ) * ( )
( F(k+1) ) ( 1 0 ) ( F(k) )
F(k) - the k-th term in Fibonacci's series

The recursive formula F(k+2) = F(k+1) + F(k) can be translated to the matrix multiplication shown above.

( F(k+2) )     ( 1  1 )     ( F(k+1) )     ( F(k+1) * 1 + F(k) * 1 )
( ) = ( ) * ( ) = ( )
( F(k+1) ) ( 1 0 ) ( F(k) ) ( F(k+1) * 1 + F(k) * 0 )

Starting from k=0, we can find the k-th Fibonacci term using the following formula:

                       ^(k-1)
( F(k) ) ( 1 1 ) ( F(1) )
( ) = ( ) * ( )
( F(k-1) ) ( 1 0 ) ( F(0) )

Exponentiation by squaring

This is a method used for determining a number a^b in lg2(b) time. This method is based on the observation that there is no need to perform b multiplications with a, but instead have two numbers stored: one with the result and one with a partial solution. The partial solution will store a¹, a², a⁴, a⁸, …

function exp(a, b) {
aux = a
res = 1;
for (i = 0; (1 << i) <= b; ++i) {
if ((1 << i) & b) {
res *= aux;
}
aux *= aux;
}
return res;
}

Example: we are interested in a²¹. We can write that as:

a²¹ = a¹⁶ * a⁴ * a¹ — because 21 & 1, 21 & 4, 21 & 16 are different than zero, while 21 & 2 = 0, 21 & 8 = 0

All that’s left is to compute a¹⁶ and a⁴. a¹⁶ can be computed in 4 steps:

  1. a² = a * a
  2. a⁴ = a² * a² — we are using this
  3. a⁸ = a⁴ * a⁴
  4. a¹⁶ = a⁸ * a⁸ — and this

Piecing it all together

( F(k+2) )     ( 1  1 )     ( F(k+1) )     ( F(k+1) * 1 + F(k) * 1 )
( ) = ( ) * ( ) = ( )
( F(k+1) ) ( 1 0 ) ( F(k) ) ( F(k+1) * 1 + F(k) * 0 )

So, in order to get our solution, we need to change the matrices that we are multiplying. We can observe that the result and the second term are just sequences of Fibonacci numbers, so we can safely extend that. The problem arises when trying to change the first term ((1, 1), (1, 0)) matrix.

The weights are smaller than 100, which means in our dynamic programming technique, we only need the last 100 members, so the single column matrices expand to:

(  dp[k]  )          ( dp[k-1] )
( dp[k-1] ) ( dp[k-2] )
( dp[k-2] ) = .... * ( dp[k-3] )
... ...
( dp[k-99]) ( dp[k-98])

Let’s disect the matrix ((1, 1), (1, 0)):

  • The first row is necessary to compute the first row in the resulted matrix. So, naturally, all the elements should be one.
  • On the second row, only a translation is needed and because the first element is one and the rest are zero, only the number on the first row in the second term is taken from.

Let’s attempt to build this matrix for a general form (where not all the previous terms form the next)

int M[100][100]; // all zeros
for (int k = 0; k < K; ++k) {
M[0][objects[k]-1] = 0;
}
for (int i = 1; i < 100; ++i) {
M[i][i-1] = 1;
}

The matrix will look like this:

( 0 1 1 0 0 1 .... 1 ) - depending on the weights of objects
( 1 0 0 0 0 0 .... 0 )
( 0 1 0 0 0 0 .... 0 )
( 0 0 1 0 0 0 .... 0 ) - identiy matrix + 1 column of zeros
( 0 0 0 1 0 0 .... 0 )
( ................ 0 )
( 0 0 0 .........1 0 )

Since we imposed that the matrix size is 100, the second term in the multiplication must be computed sequentially => 100 operations.

The solution is finally given by

(  dp[N]  )              ( dp[99] )
( dp[N-1] ) ( dp[98] )
( dp[N-2] ) = M^(N-99) * ( dp[97] )
.......... ..........
( dp[N-98]) ( dp[1] )
( dp[N-99]) ( dp[0] )

Memory: O(max(weights)²), Complexity: O(lg2(N)*max(weights)³)

Conclusions

There are two main takeaways from this article:

  • Optimizing for different sets of requirements yields very different approaches and solutions
  • I had too much spare time writing this

--

--