algorithm research (bin-packing-esque)

example.md

The purpose of this gist is to become aware of algorithms or existing solutions that I'm currently unaware of (I want to know what I don't know).

Below are some constraints and a few example problems leveraging said constraints. I believe the constraints and example problems are heavily related to bin-packing, but if anyone has additional info to steer me toward better algorithms or solutions that would be ideal.

Constraints:

• container with set width and height
• n number of items
• n number of display styles
• account for padding between items (but not container edges)
• fit all items in the container with no empty space
• breaking from the display styles for a subset of items is allowed in order to fill empty space

Example Problem:

1. You are given a 2D container of size 1000x600. You have 15 items that can be packaged in various sizes that meet a particular display style. The display styles are 1x1, 1x2, 2x1, and 2x2. Provide an algorithm that creates solutions (many solutions will exist) for fitting all 15 items within the 1000x600 confines where no empty space exists. Ideally the display styles are evenly distributed. It is OK to break from the display style constraints for a small subset of the items in order to properly fit (with no empty space) all items in the container.

2. Solve the same problem with an added constraint of a padding value of 10 between items where no padding at the container edges is acceptable.

3. Solve the same problem where 7 of the 15 items have a preference of the display style 1x2.

Rough Solution (naive?):

My gut is that a solution could work using two core steps:

1. bin packing
2. back-track items that exceed or come short and resize them to fit