1

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

例如，第 1 节高 250 磅，第 2 节高 650 磅。如果用户选择：

400 分来自表格 a 部分的
内容 200 分来自 b 部分
的内容 250 分来自表格 c 的内容
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我应该如何做这件事？谢谢！

更新：

这是布局的粗略轮廓，以便您可以获得更清晰的图片。

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

这两个图像总是在同一个位置和相同的大小。
还应该注意的是，这是用于 PDF 制作，而不是 Web 使用，因此 CSS 和 Javascript 不是选项。我正在使用的环境仅允许使用 Python 代码。

4

1 回答 1

3

基本上，这是一个接一个地解决每个部分的背包问题（长度作为值和权重）。我将为此使用蛮力，但您可以查找它并找到其他在速度方面更有效的方法，但可能无法提供最佳解决方案 - 这个可以。

有2^b（b块的数量）组合来填充第一部分，因为对于每个块，您可以将其放入其中或不放入其中。只有其中的一个子集是可行的。您选择填充最多的组合。然后你重复下一部分的剩余项目。

这应该让您知道如何做到这一点：

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 次迭代。在如此小的规模上，蛮力通常不是问题。但是，增加块的数量会对性能产生巨大影响！

于 2013-05-24T21:59:14.840 回答