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.

Cheers - L~R

In reply to Challenge: Twist On Bin Packing by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.