5

I'm trying to solve a problem, so I'm not looking for code, but for similar algorithms so I can solve it myself.

I am given n bookcases each with a size amount of books inside. I am to move some of these bookcases to a new room as follows:

  • The first bookcase will always be moved;
  • I will keep the order of the bookcases in the new room (I can't change positions in the new room);
  • Bookcase i cannot be placed next to either of the bookcases i-1 or i+1 (ex: I can't place ?-4-5-?/?-5-6-?/?-4-5-6-?);

So bookcase 1 is always in the new room. Furthermore, if bookcase i is in the room, then neither i-1, nor i+1 will be in the room.

Which configuration of bookcases will offer me the largest amount of books?

I understand that this is solved using a dynamic programming algorithm, but I am not sure which one. I initially thought it would be similar to the knapsack problem, but I don't have a limit of books so it's clearly different (at least I think it is). The target complexity is O(n), but any idea that will help me will do.

Robert Harvey
  • 198,589
  • 55
  • 464
  • 673
Xzenon
  • 167
  • 3
  • Your phrasing is a tiny bit unclear, and it's critical we understand the exact problem before answering, so can you confirm that this rephrasing of mine is what you have in mind? "I have bookcases 1 through n, each containing some number of books. I must select which bookcases to place in the new room so that the new room contains the largest possible number of books, subject to two constraints: 1) Bookcase 1 must go in the new room. 2) If bookcase x is in the new room, then bookcases x-1 and x+1 cannot be in the new room." – Ixrec Mar 15 '16 at 22:41
  • That is correct. I'll try to rephrase my question. – Xzenon Mar 15 '16 at 22:42
  • 2
    Please do not cross-post: it is better to delete one of the questions. –  Mar 15 '16 at 22:42

1 Answers1

1

This problem is similar to the longest increasing subsequence problem. Say we store the number of books inside each bookcase in an array N.

N[i] = number of books in bookcase i.

You keep an array S, where S[i] is the maximum value you can get to the other room using a subset of the items 1 to i which contains item i.

S[ 1 ] = N[ 1 ]

S[ i ] = max( S[ 1 ], S[ 2 ], ... S[ i - 2 ] ) + N[ i ], for i = 3..N.Size

The answer will then be the value max(S[N.Size], S[N.Size - 1]). To get the actual items that you take you can keep additional information in another array PREV[i] - The item before i in the new room.

This runs in O(n^2) time but you can improve that to O(nlogn) by using interval trees or binary indexed trees to get the maximum in logarithmic time (similar to the longest increasing subsequence problem)

Update: Just realized that if the values are positive then we can solve this in O(n)

S[i] =max(S[i-2], S[i-3]) + N[i]

But if the values can be negative then this will not work

Adrian Buzea
  • 273
  • 2
  • 9