Fill an area with best fitting "blocks"

Question

I have some code that generates blocks of text based on a user's selection. The height of these text blocks varies on how many items the users selected. What I am trying to do is ensure that these blocks are arranged on the page in the most efficient manner.

For example, section 1 is 250 points tall and section 2 is 650 points tall. If the user chooses:

400 points worth of content from part a of the form
200 points of content from part b
250 points of content from part c
50 points of content from part d

How can I make sure that part b and part d go into section 1 and part a & c go into section 2?

Here is my code so far:

section1_height = 250
section2_height = 650

#list1 and list2 are the variables that contain the user selections
Column1 = DWIMBLOCK([list1], (18, 430), (LEFT, TOP_BASELINE), (250, 250))
Column2 = DWIMBLOCK([list2], (275, 430), (LEFT, TOP_BASELINE), (250, 650))

columns = [Column1, Column2]
sec1_columns = []
sec2_columns = []

for column in columns:
 if column.height <= 250:
  sec1_columns.append(column)

for shorts in sec1_columns:
 if #This is where I am stuck

As you can see, I've divided my columns into those that are less than 250 points tall, but now I am stuck trying to do something along the lines of if sum of any number of blocks <= 250, assign those blocks to a new list How should I go about doing this? Thanks!

UPDATE:

Here is a rough outline of the layout, just so you can get a clearer picture.

____________________
|#########**********|
|# image #*        *|
|#########*        *|
|**********        *|
|*       **        *|
|*sec. 1 **        *|
|*       **sec. 2  *|
|**********        *|
|#########*        *|
|#       #*        *|
|# image #*        *|
|#       #*        *|
|#########**********|
____________________

The two images are always in the same spot and the same size.
It should also be noted that this is for PDF production, not web use, so CSS and Javascript are not options. The environment that I am working with allows for Python code only.

Answer 1

Basically this is solving the Knapsack problem (with lengths as both values and weights) for each section, one after another. I will use brute force for this, but you can look it up and find other methods which are more efficient in terms of speed, but may not give an optimal solution - this one does.

There are 2^b (b being the number of blocks) combinations to fill the first section, because for each block you can either put it in there or not put it in there. Only a subset of those will be feasible. You pick the combination that fills the most. Then you repeat with the remaining items for the next section.

This should give you an idea how to do it:

from itertools import combinations, chain

unassigned_blocks = {
    ('a', 400),
    ('b', 200),
    ('c', 250),
    ('d',  50),
    # ...
}

sections_and_assigned_blocks = {
    ('1', 250): {},
    ('2', 650): {},
    # ...
}

for section in sorted(sections_and_assigned_blocks.keys()):
    best, best_length = {}, 0
    for combination in chain(*[combinations(unassigned_blocks, n)
                               for n in xrange(1, len(unassigned_blocks)+1)]):
        combination = set(combination)
        length = sum(block[1] for block in combination)
        if best_length < length <= section[1]:
            best, best_length = combination, length
    sections_and_assigned_blocks[section] = best
    unassigned_blocks -= best

from pprint import pprint
pprint(sections_and_assigned_blocks)
# {('1', 250): set([('c', 250)]),
#  ('2', 650): set([('a', 400), ('b', 200), ('d', 50)])}

Time complexity is O(s*2^b) (s being the number of sections). In the worst case scenario, sections 1-3 being too small to contain anything, there will be 4 * 2^15 = 131072 iterations. On such small scale, brute force is generally not a problem. However, increasing the number of blocks has a dramatic effect on performance!