3

どのように質問すればよいかわかりませんが、できるだけ具体的にお答えください。さまざまな形の長方形だけが下に落ちているテトリス画面を想像してみてください。重なり合うことなく隣り合わせに収まる長方形の最大数を計算したいと思います。タイトルで線と名付けました。実際には、計算時の長方形の長さ、または x 軸に平行な線にのみ関心があるためです。

したがって、基本的には、開始と終了が両方とも 0 から 100 までの整数であるカスタム タイプがあります。1 から n の範囲のこれらの長方形のリストがあるとします。重ならないように、rectangle_n.start (原点に最も近い長方形でない限り) は >rectangle_(n-1).end でなければなりません。乱数を含むファイルから長方形の座標 (両方とも x 軸座標) を読み取っています。

例として、この長方形タイプのオブジェクトのリストを考えてみましょう

rectangle_list {start, end} = {{1,2}, {3,5}, {4,7} {9,12}}

3 番目のオブジェクトの開始座標は 4 < 前の四角形の終了座標である 5 であることがわかります。したがって、このリストをソートする際に、2 番目または 3 番目のオブジェクトが重ならないように削除する必要があります。

この種の問題にタイプがあるかどうかわからないので、他に名前を付ける方法がわかりませんでした。そのようなオブジェクトのリストに適用でき、それに応じてそれらを分類するアルゴリズムに興味があります。

私が書いているコードは c++ ですが、どの言語でもアルゴリズムを実行できるため、これに c++ のタグを付けました。 初期状態

最終状態

4

3 に答える 3

3

この問題の名前はビン パッキングです。通常は難しい問題と見なされますが、ビンの数が少ない場合は適切に計算できます。

これは、この問題に対する一般的なアプローチを説明するビデオです

編集：難しい問題とは、ある種のブルートフォースを採用する必要があることを意味します。多くのソリューションを評価し、それらのほとんどを拒否する必要があるため、通常は何らかの評価メカニズムが必要です。「このソリューションは、面積が 15 の 4 つの長方形をパックします」などのソリューションを比較できる必要があります。「このソリューションは、面積が 16 の長方形を 3 つパックします」よりも優れています。

于 2013-06-04T21:04:35.530 に答える
2

近道は考えられないので、サイズの降順でパワーセットを列挙し、最初の一致で停止する必要があるかもしれません。

これを行う簡単な方法は、減少するサイズの組み合わせを列挙することです。C++11 では、次のようなことができます。

template <typename I>
std::set<Span> find_largest_non_overlapping_subset(I start, I finish) {
    std::set<Span> result;
    for (size_t n = std::distance(start, finish); n-- && result.empty();) {
        enumerate_combinations(start, finish, n, [&](I begin, I end) {
            if (!has_overlaps(begin, end)) {
                result.insert(begin, end);
                return false;
            }
            return true;
        });
    }
    return result;
}

の実装はenumerate_combination演習として残します。私はあなたがすでに持っていると仮定しますhas_overlap。

于 2013-06-04T21:08:18.763 に答える