All,
If you are not familiar with the bin packing problem, it is the daunting (NP Hard) task of cramming a certain number of items into the fewest bins possible where each bin has a fixed capacity. A not too uncommon question here at the Monastery is how to minimize the number of CDs needed to burn all music files. I have been thinking about an interesting twist on the problem.

What if instead of trying to minimize the number of bins used you were trying to mazimize them. For instance, you wanted to make it look like you had purchased more gifts that you actually had. Presuming that every gift could fit into a single shipping box then you could send each gift in its own box. While this is obviously the maximum number of bins (provided you don't send any empty boxes) people are going to immediately see through your ruse.

Instead, you fill each box as close to capacity as possible but without doing it as efficiently as possible. Sound odd? I thought so too at first. It is easily reconciled when you consider that any attempt at solving the bin packing problem that is not the optimal solution is a series of bins as near capacity as possible without being as efficient as possible.

Imagine that a shipping box can only hold 10 units of weight and you have purchased 7 gifts with weights of 2, 2, 3, 4, 5, 6, and 7. You could get away with sending only 3 boxes by arranging them as:

1:  7, 3
2:  6, 4
3:  5, 2, 2
[download]

Instead, you send 4 and everyone is impressed with your generosity:

1:  7, 2
2:  5, 4
3:  6, 3
4:  2
[download]

My challenge then is to come up with an algorithm that provides the most inefficient solution to the bin packing problem while requiring that each bin be filled as near to capacity as possible. Update: This means you start filling the first bin until no more items will fit. Move on to second bin and repeat the process. The goal is to end up with as many bins as possible not the fewest.

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.