This may not be a question all about Perl, but ya'll are the smartest people I know, so I was hoping someone could help me through this.

I have a double array of rectangles.   Each rectangle has an x and a y coordinate.   I have an area of MaxX by MaxY to be filled.   Lets just say I am trying to fit these rectangles on an 8.5 by 11 piece of paper.   So MaxX = 8.5 and MaxY = 11.   I have to have a line that divides the paper in two.   This line can be either vertical or horizontal.

These rectangles can be turned either way, so we do not have to worry about x's and y's.   My priorities are to have the largest area taken, and to hopefully go from one edge of the paper to the other, without having any scrap.   For example, there are 4, 2.75 by 3 rectangles and 4, 3 by 3 rectangles.   I would want to use the 4, 2.75 by 3 rectangles because the height of all of the rectangles stacked up is 11, thus we can have a solid line vertically with zero scrap.   So I am looking to find the largest area with the least amount of scrap.   If there are two possibilites that have zero scrap, then the one with the largest area will be the one chosen.   If there are none with zero scrap, then the one with the least amount of scrap will be chosen.  If there is a tie between ones with the least amount of scrap, then the one with the largest amount of area will be chosen.

That is my problem, I am looking for as much help as possible.   I really do not know how to loop through the array and choose the best one, and then look through again looking to see if there is a better one.   I hope that this is not confusing and that someone can help. Thanks in advance.

janitored by ybiC: Retitle from "Grasping the concept"

In reply to Knapsack problem by stu96art

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.