10

3 インチ× 1 インチと 4.5 インチ× 1 インチのブロックを使用してパネルを作成するためのブロックのセットが提供されます。

構造上の完全性を確保するために、ブロック間のスペースが隣接する列に並ばないようにする必要があります。

7.5インチ×1インチのパネルを組み立てる方法は2つ、7.5インチ×2インチのパネルを作る方法は2つ、12インチ×3インチのパネルを作る方法は4つ、27インチ×5インチのパネルを作る方法は7958通りあります。 」パネル。48 インチ×10 インチのパネルを構築するには、いくつの方法がありますか?

これは私がこれまでに理解していることです：

ブロック3 x 1および4.5 x 1を使用

組み合わせ式を使用して、2 つのブロックをこのサイズのパネルに配置できるすべての可能な組み合わせを見つけました。

C = 選択 --> C(n, k) = n!/r!(nr)! 一度に r のグループ n の組み合わせ

パネル: 7.5 x 1 = 2 ウェイ-->

1 (3 x 1 ブロック) と 1 (4.5 x 1 ブロック) --> 2 ブロックのみ使用 --> 2 C 1 = 2 ウェイ

パネル: 7.5 x 2 = 2 ウェイ

ここでもコンビネーションを使いました

1 (3 x 1 ブロック) と 1 (4.5 x 1 ブロック) --> 2 C 1 = 2 ウェイ

パネル: 12 x 3 パネル = 2 ウェイ-->

2(4.5 x 1 ブロック) と 1(3 x 1 ブロック) --> 3 C 1 = 3 ウェイ

0(4.5 x 1 ブロック) と 4(3 x 1 ブロック) --> 4 C 0 = 1 ウェイ

3通り＋1通り＝4通り

（ここで迷うところです）

パネル 27 x 5 パネル = 7958 ウェイ

6(4.5 x 1 ブロック) と 0(3 x 1) --> 6 C 0 = 1 ウェイ

4(4.5 x 1 ブロック) と 3(3 x 1 ブロック) --> 7 C 3 = 35 ウェイ

2 (4.5 x 1 ブロック) と 6 (3 x 1 ブロック) --> 8 C 2 = 28 ウェイ

0(4.5 x 1 ブロック) と 9(3 x 1 ブロック) --> 9 C 0 = 1 ウェイ

1 ウェイ + 35 ウェイ + 28 ウェイ + 1 ウェイ = 65 ウェイ

ここでわかるように、ウェイの数は 7958 にはほど遠いです。ここで何が間違っているのでしょうか?

また、48 x 10 のパネルを作成する方法はいくつあるのでしょうか? 特に 7958 の方法を見つけようとする場合、手動で行うのは少し難しいためです。

7958 パネルのウェイ数の答えを計算するプログラムをどのように作成しますか? 結果を計算するプログラムを作成する方が簡単でしょうか? どんな助けでも大歓迎です。

4

5 に答える 5

4

「ブロック間のスペースが隣接する行に並んではならない」という要件を考えると、「選択」機能が直接適用できるとは思いません。また、これがあなたの分析が崩壊し始める場所だと思います：

パネル: 12 x 3 パネル = 2 ウェイ -->

2(4.5 x 1 ブロック) と 1(3 x 1 ブロック) --> 3 C 1 = 3 ウェイ

0(4.5 x 1 ブロック) と 4(3 x 1 ブロック) --> 4 C 0 = 1 ウェイ

3通り＋1通り＝4通り

...いくつかのパネルを作成しましょう (1 |= 1 行、2 -'s = 1 列):

+---------------------------+
|      |      |      |      |
|      |      |      |      |
|      |      |      |      |
+---------------------------+

+---------------------------+
|          |         |      |      
|          |         |      |      
|          |         |      |      
+---------------------------+

+---------------------------+
|      |          |         |            
|      |          |         |      
|      |          |         |      
+---------------------------+

+---------------------------+
|          |      |         |                  
|          |      |         |      
|          |      |         |      
+---------------------------+

ここでは、4 つの異なる基本的な行タイプがあることがわかりますが、これらのいずれも有効なパネルではありません (それらはすべて「ブロックを並べてはならない」規則に違反しています)。ただし、これらの行タイプを使用して複数のパネルを作成できます。

+---------------------------+
|      |      |      |      |
|      |      |      |      |
|          |         |      |      
+---------------------------+

+---------------------------+
|      |      |      |      |
|      |      |      |      |
|      |          |         |      
+---------------------------+

+---------------------------+
|      |      |      |      |
|      |      |      |      |
|          |      |         |     
+---------------------------+

+---------------------------+
|          |         |      |      
|          |         |      |
|      |      |      |      |
+---------------------------+

+---------------------------+
|          |         |      |      
|          |         |      |
|      |          |         |
+---------------------------+

+---------------------------+
|          |         |      |      
|          |         |      |
|          |      |         |
+---------------------------+

...

しかし、繰り返しますが、これらはどれも有効ではありません。有効な 12x3 パネルは次のとおりです。

+---------------------------+
|      |      |      |      | 
|          |      |         |
|      |      |      |      |
+---------------------------+

+---------------------------+
|          |      |         |
|      |      |      |      |
|          |      |         |
+---------------------------+

+---------------------------+
|          |         |      |
|      |          |         |
|          |         |      |
+---------------------------+

+---------------------------+
|      |          |         |
|          |         |      |
|      |          |         |
+---------------------------+

実際には 4 つありますが、この場合、「選択」機能を使用して取得したものと一致するのは単なる偶然です。合計パネル構成に関しては、4 をはるかに超えています。

于 2011-07-11T04:15:56.913 に答える
3

  1. 指定された幅の単一の行を形成するすべての方法を見つけます。私はこれを「行型」と呼んでいます。 例 12x3: 幅 12 の 4 つの行タイプがあります: (3 3 3 3)、(4.5 4.5 3)、(4.5 3 4.5)、(3 4.5 4.5)。 これらをギャップのリストとして表します。 例: (3 6 9), (4.5 9), (4.5 7.5), (3 7.5).

  2. これらの行の種類ごとに、その上に収まる他の行の種類を見つけます。

    例：

    a. フィット(3 6 9)します(4.5 7.5)。

    b. フィット(4.5 9)します(3 7.5)。

    c:(4.5 7.5)フィットします(3 6 9)。

    d:(3 7.5)ぴったり(4.5 9)。

  3. これらのルールから、指定された高さのスタックを構築する方法を列挙します。これには動的計画法が適用されます。各レベルでは、最後の行の型とそこに到達する方法の数だけが必要です。

編集：コーヒーブレイクでこれを試したところ、うまくいきました。ちなみに、48x10 の解は 10 進数で 15 桁です。

編集：動的プログラミング部分の詳細は次のとおりです。

ステップ 2 のルールは、可能な近隣の配列に変換されます。配列の各要素は行タイプに対応し、その行タイプの可能な隣接行タイプのインデックスを保持します。

0: (2)
1: (3)
2: (0)
3: (1)

12×3 の場合、各行タイプには可能な隣接行タイプが 1 つしかありませんが、一般的には複数の行タイプを使用できます。

動的計画法は 1 つの行から始まります。各行の型には 1 つの表示方法があります。

1 1 1 1

次に、次の行は、行タイプごとに、前の行で形成された可能性のある隣接ウェイの数を追加することによって形成されます。幅が 12 の場合も、結果は次の1 1 1 1ようになります。最後に、最後の行を合計します。

複雑：

  • 行の型を見つけることは、ツリーの葉を列挙することに相当します。このツリーには約(/ width 3)レベルがあるため、これにはO(2 w/3 ) = O(2 w )の時間がかかります。

  • 2 つの行の型が適合するかどうかを確認するには、それらの長さに比例してO(w/3)の時間がかかります。クロス テーブルの作成は、行の種類の数の 2 乗に比例します。これにより、ステップ 2 O(w/3·2 2w/3 ) = O(2 w )が作成されます。

  • 動的計画法では、高さ×行タイプの数×近傍の平均数 (行タイプの数の対数であると推定されます)、O(h·2 w/3 ·w/3) = O(2 w）。

ご覧のとおり、これはすべて、幅に応じて指数関数的に増加する行タイプの数によって支配されています。幸いなことに、定数係数はかなり低いので、48×10 は数秒で解くことができます。

于 2011-07-11T07:02:10.057 に答える
1

これは「2d ビン パッキング」の問題です。まともな数学的知識を持っている人が助けてくれるか、計算アルゴリズムに関する本を試すことができます。これは「組み合わせ NP 困難問題」として知られています。それが何を意味するのかわかりませんが、「難しい」部分が私の注意を引きます:)

私は鋼の切断プログラムを見てきましたが、ほとんどの場合、最良の推測を使用しています。この場合、2 x 4.5 インチを垂直に積み重ねても、3 x 3 インチを水平に積み重ねることができます。無駄なく乗り切れるかもしれません。無駄を最小限に抑えた最適なソリューションを見つけなければならない場合は、ややこしい作業になります。

于 2011-07-11T04:31:20.863 に答える
1

これは、再帰的に解決できるタイプの問題のように見えます。前のレイヤーと残りのレイヤーの数を引数として受け入れる再帰的メソッドを使用して、使用できるアルゴリズムの簡単な概要を次に示します。

  • レイヤーの初期数 (例: 27x5 は、remainingLayers = 5 で開始) と空の前のレイヤーから開始します。
  • 現在のレイヤーのすべての可能なレイアウトをテストします
    • 構築中のレイヤーで次に使用可能なスロットに 3x1 を追加してみてください。(a) ターゲット幅を超えていないこと (たとえば、27x5 で 27 幅を超えていないこと)、および (b) 前のレイヤーで指定された間隔条件に違反していないことを確認します。
    • 正確に (たとえば) 27 ユニット幅の有効なレイヤーが構築されるまで、現在のレイヤーに 3x1 を追加しようとし続けます。
    • 現在のスロットで 3x1 を使用できない場合は、それを取り外して 4.5x1 に置き換えます。
    • 有効なレイヤーを取得したら、remainingLayers をデクリメントし、構築したばかりのレイヤーと共に再帰アルゴリズムに戻します。
  • 残りのレイヤー = 0 に達すると、有効なパネルが作成されたので、カウンターをインクリメントします。

アイデアは、有効なレイヤーの可能なすべての組み合わせを構築することです。(27x5 の例では) 5 つの有効なレイヤーを互いに重ねると、完全な有効なパネルが構築されます。そのため、アルゴリズムは、可能なすべての有効なパネルを 1 回だけ検出 (およびカウント) する必要があります。

于 2011-07-11T03:47:35.087 に答える
0

これがJavaの解決策です。配列の長さのチェックなどのいくつかは少し面倒ですが、かなり簡単に改良できると確信しています。

いずれにせよ、これがアルゴリズムの仕組みを示すのに役立つことを願っています:-)

import java.util.Arrays;

public class Puzzle
{
    // Initial solve call
    public static int solve(int width, int height)
    {
        // Double the widths so we can use integers (6x1 and 9x1)
        int[] prev = {-1};      // Make sure we don't get any collisions on the first layer
        return solve(prev, new int[0], width * 2, height);
    }

    // Build the current layer recursively given the previous layer and the current layer
    private static int solve(int[] prev, int[] current, int width, int remaining)
    {
        // Check whether we have a valid frame
        if(remaining == 0)
            return 1;

        if(current.length > 0)
        {
            // Check for overflows
            if(current[current.length - 1] > width)
                return 0;

            // Check for aligned gaps
            for(int i = 0; i < prev.length; i++)
                if(prev[i] < width)
                    if(current[current.length - 1] == prev[i])
                        return 0;

            // If we have a complete valid layer
            if(current[current.length - 1] == width)
                return solve(current, new int[0], width, remaining - 1);
        }

        // Try adding a 6x1
        int total = 0;
        int[] newCurrent = Arrays.copyOf(current, current.length + 1);
        if(current.length > 0)
            newCurrent[newCurrent.length - 1] = current[current.length - 1] + 6;
        else
            newCurrent[0] = 6;
        total += solve(prev, newCurrent, width, remaining);

        // Try adding a 9x1
        if(current.length > 0)
            newCurrent[newCurrent.length - 1] = current[current.length - 1] + 9;
        else
            newCurrent[0] = 9;
        total += solve(prev, newCurrent, width, remaining);

        return total;
    }

    // Main method
    public static void main(String[] args)
    {
        // e.g. 27x5, outputs 7958
        System.out.println(Puzzle.solve(27, 5));
    }
}
于 2011-07-11T04:36:31.747 に答える