用最合适的“积木”填充一个区域

Question

我有一些代码可以根据用户的选择生成文本块。这些文本块的高度取决于用户选择的项目数。我要做的是确保这些块以最有效的方式排列在页面上。在

例如，截面1的高度为250点，截面2的高度为650点。如果用户选择：

表格a部分内容价值400分
200分b部分的内容
c部分250分内容
d部分50分内容

如何确保b部分和d部分进入第1部分，a和c部分进入第2部分？在

以下是我目前为止的代码：

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

正如您所看到的，我已经将我的专栏分成了不到250个点高的专栏，但是现在我被困在试图按照if sum of any number of blocks <= 250, assign those blocks to a new list的思路来做一些事情，我该如何着手做呢？谢谢！在

更新：

这是一个粗略的布局轮廓，这样你可以得到一个更清晰的画面。在

^{pr2}$

这两张图片总是在同一个位置，大小相同。
还应该注意的是，这是为了PDF制作，而不是web使用，所以CSS和Javascript不是选项。我使用的环境只允许使用Python代码。在

Answer 1

基本上，这是解决背包问题（以长度为价值和重量）为每个部分，一个接一个。我将使用暴力来解决这个问题，但是你可以查一下，找到其他在速度上更有效的方法，但是可能不会给出一个最佳的解决方案-这一个可以。在

{{cd2>你可以把它放在第一个块中。只有其中的一部分是可行的。你选择最适合的组合。然后对下一部分的其余项目重复。在

这会让您了解如何进行：

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)])}

时间复杂度是O(s*2^b)（s是段数）。在最坏的情况下，第1-3节太小而不能包含任何内容，将有4*2^15=131072次迭代。在如此小的范围内，暴力一般不是问题。但是，增加块的数量会对性能产生显著的影响！在