2 つの行が必要な場合を考えてみましょう。リスト内の可能なすべての分割ポイント (インデックス) をテストし、どれが最良の結果をもたらすかを確認できます (最大行幅を最小化します)。
3 行以上の場合は、以下のコード サンプルに示すように、再帰を使用して "右半分" を分割し続けます。(パイソン)
def split(sizes, count):
# base case: one row, just return it
if count == 1:
return [sizes]
best_score = None
best_result = None
# for each possible split point (don't allow empty rows)
for i in range(1, len(sizes)):
# the first row is the columns up to the split point
left = [sizes[:i]]
# recurse to process the remaining rows
right = split(sizes[i:], count - 1)
if right is None:
# failed to split count - 1 times, ignore
continue
rows = left + right
# minimize the maximum row width
score = max(sum(row) for row in rows)
if best_score is None or score < best_score:
best_score = score
best_result = rows
return best_result
if __name__ == '__main__':
sizes = [100, 50, 100, 50, 50, 50]
print split(sizes, 2)
print split(sizes, 3)
出力:
[[100, 50], [100, 50, 50, 50]] # 2 rows
[[100], [50, 100], [50, 50, 50]] # 3 rows