3
$\begingroup$

Sorry for layman's term question, my background in computer science is weak.

What I have is a list of shelves with books of varying height. Each shelf stores a value that describes how many shelves (of that height) can fit on a bookcase. The bookcases have adjustable shelves so that we can maximize the usage of each one.

What I have been trying so far is sorting the shelves from shortest to tallest and filling in each bookcase, but what happens is that there are remainders which could be filled in with the small shelves.

I should mention that an additional complexity is that we want to place the tallest shelf on the top of the bookcase (because it would be more efficient).

I am not expecting a full on answer for how to do this... but I would very much appreciate a book or article on the topic. I just need a little direction and I think I would be able to pick it up.

Thanks for your help!

$\endgroup$
  • 1
    $\begingroup$ I have found that the problem I am describing is called a "Packing Problem" and that I am looking for a one-dimensional solution. The idea I had to solve it is actually a non-optimal solution called the "first-fit algorithm". More information here: en.wikipedia.org/wiki/Bin_packing_problem $\endgroup$ – Primalpat Jan 30 '15 at 21:43
3
$\begingroup$

I'm not clear on whether you have one bookcase or multiple bookcases, so I'll explain how to handle both cases below.

Multiple bookcases

If you have multiple bookcases, and you need to put each shelf into exactly one of the bookcases, then you have an instance of the bin packing problem.

Each shelf corresponds to an item, and each bookcase corresponds to a bin. Now you want to find a way to put each item into one bin, i.e., put each shelf into one bookcase, so that every shelf is in some bookcase, and each bookcase has room for all the shelves that will go into it.

This can be modelled in a straightforward way as a bin packing problem:

  • The "size" of a shelf (an item) is the height of the shelf.

  • The "size" of a bookcase (i.e., of a bin) is the height of the bookcase.

Now you want to find a way to assign each shelf to one of the bookcases, so that the sum of the sizes (heights) of the shelves in each bookcase does not exceed the size (height) of the bookcase. That is exactly the bin packing problem.

You should be able to use any standard algorithm for bin packing to solve your problem. Given the number of bookcases and shelves you're likely to have in practice, any of them should be efficient enough for practical use. For instance, one approach is to formulate this as an instance of ILP (integer linear programming), as described in the Wikipedia article on bin packing, and then solve the problem using an off-the-shelf ILP solver, such as lp_solve or CPLEX. This will likely be very effective in practice.

All of these algorithms can accommodate the requirement to put the tallest shelf on the top: you select the set of shelves to go into each bookcase, and then for each bookcase, find the tallest of the shelves that are going into that bookcase and put it at the top of the bookcase.

One bookcase

If you have one bookcase, and you can select some subset of the shelves to fill the bookcase, your problem is an instance of the knapsack problem.

Treat each shelf as an item that can be placed into the knapsack. Then:

  • the "weight" of a shelf is its height,

  • the "value" of a shelf is the value of including that shelf in the bookcase (e.g., the number of books it'll enable you to store, or maybe just a fixed value that's the same for all shelves), and

  • the "capacity" of the knapsack is the total height of the bookcase.

The optimal solution to the knapsack problem will select a subset of items whose total weight doesn't exceed the knapsack's capacity, and that maximizes the sum of the values of the selected items.

In your context, that amounts to selecting a subset of the shelves whose total height doesn't exceed the height of the bookcase (and thus it'll be possible to fit all of the selected shelves into your bookcase), and that maximizes the sum of the values of the shelves (e.g., maximizes the total number of shelves that you fit into the bookcase, or the total number of books you can store in the bookcase, etc.).

There are many algorithms for the knapsack problem, such as the dynamic programming algorithm. In your situation, I suspect the number of candidate shelves is small enough that any of these algorithms is likely to be efficient enough for real-world use.

All of these algorithms can accommodate the requirement to put the tallest shelf on the top: you select the set of shelves to go into the bookcase, and then choose the one that is tallest and put it at the top of the bookcase.

$\endgroup$
  • $\begingroup$ This is an incredibly helpful answer. I am in the multiple bookcase scenario. Thank you for your time! $\endgroup$ – Primalpat Feb 1 '15 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.