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(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 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.