1

基本的に、次の幅の 5 つのアイテムがあるとします (高さはこれにはあまり関係ないので、すべての高さが 50 ピクセルであるとしましょう)。

  1. 50
  2. 100
  3. 100
  4. 100
  5. 50

そして、それらをできるだけ均等に2つの異なる行に分割したいと思います(その順序である必要があります)。これを行うために行の最小幅を計算するにはどうすればよいですか?

: すべての幅を合計して行数で割るだけでは簡単ではありません。上記の例でそれを行うと、幅の合計 (400) が行数で割られるため、項目が収まりません。行 (2) は 200 (400 / 2 = 200) です。この場合、5 番目の項目はどの行にも収まりません。

先ほど述べた方法を使用するとうまくいかない別の例を次に示します。

  1. 100
  2. 50
  3. 100
  4. 50
  5. 50
  6. 50

この場合、最後の 2 つの項目 (5 と 6) には追加の行が必要になります。

AC# のサンプルは、私がこれを行うために使用している言語であるため、非常に優れています =)。

ありがとう!

4

3 に答える 3

3

N幅の項目を width{W[i]}R行に合わせようとしているとしましょうC。あなたRは固定されていますが、あなたCは不明です。

まず、いくつかの重要な観察事項を確認しましょう。

  • が与えられた場合、その特定のものを選択すると配置が正確に行になるかどうかをC簡単に確認できます。項目を 1 つずつ調べて、現在の合計を計算し、カットオフ ポイントとして使用することで確認できます。CRC
  • の最小値はC最小W[i]です。最大値はW[i]sの合計です
  • 増やすCことで必要な行数を減らすことはできますが、増やすことCはできません。したがって、関数RequiredRows(C, W[0..N])単調です。

これらの観察結果は、単純なアルゴリズムにつながります。二分探索の各ステップで現在の合計に基づいてチェッカーを実行するCこと により、最小の二分探索を実行します。RequiredRows(C, W[0..N]) == R

C# での骨組みの実装を次に示します。

private static int RequiredRows(int C, int[] data) {
    var res = 1;
    var total = 0;
    foreach ( var w in data) {
        if (total+w <= C) {
            total += w;
        } else {
            res++;
            total = w;
        }
    }
    return res;
}
public static void Main() {
    var data = new[] {50,100,100,100,50};
    var R = 2;
    var start = data.Max();
    var end = data.Sum();
    while (start+1 < end) {
        var mid = start+((end-start)/2);
        if (RequiredRows(mid, data) > R) {
            start = mid;
        } else {
            end = mid;
        }
    }
    Console.WriteLine(end);
}
于 2012-05-30T20:02:36.067 に答える
1

順序が固定されていて、ちょうど 2 つの行がある場合、これはかなり簡単な問題です。幅の配列を累積配列に変換します。最初の例では、次のようになります。

  1. 50
  2. 150
  3. 250
  4. 350
  5. 400

2番目の場合は次のようになります。

  1. 100
  2. 150
  3. 250
  4. 300
  5. 350
  6. 400

次に、最後のエントリの半分に最も近いエントリを検索し、そのエントリの直後でリストを 2 つに分割します。同点を任意に解決します (したがって、どちらの例でも項目 2 または 3 の後)。最小行幅は、エントリの累積幅の最大値、またはそれと合計幅 (最後の累積エントリ) との差です。

于 2012-05-30T20:02:28.783 に答える
0

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
于 2012-05-30T20:04:55.883 に答える