1

ユーザーの選択に基づいてテキストのブロックを生成するコードがあります。これらのテキスト ブロックの高さは、ユーザーが選択したアイテムの数によって異なります。私がやろうとしているのは、これらのブロックが最も効率的な方法でページに配置されるようにすることです。

たとえば、セクション 1 の高さは 250 ポイントで、セクション 2 の高さは 650 ポイントです。ユーザーが選択した場合:

フォームのパート a の 400 ポイント相当の内容
パート b の内容 200 ポイント
パート 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どうすればよいですか?」ありがとう！

アップデート：

より明確なイメージを得ることができるように、レイアウトの大まかな概要を次に示します。

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

2 つの画像は常に同じ場所にあり、同じサイズです。
また、これは Web での使用ではなく PDF の生成用であるため、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 に答える