長さのネスティングに問題があります。これを解決する最善の方法を教えてください。私の問題は次のとおりです。
全長と言う標準的な長さがあります(これは、特定の長さのブロックで埋める必要がある全長です)
入力は長さブロックのリストです。例: 5000、4000、3000
各ブロック間のギャップは範囲です。例: 200 から 500 (このギャップは範囲内で調整できます)
ここで、各ブロック間にギャップがある上記の利用可能な長さブロックで全長を埋める必要があり、そのギャップは上記のギャップ範囲内にある必要があります。
この問題を解決する方法を教えてください。
少し早いですがお礼を...
よろしく、 アニル
この問題は、本質的に、小さなひねりを加えた部分和問題です。サブセット合計と同じ疑似多項式時間ソリューションを使用できます。長さ「合計長」の配列を作成し (これ以降、 nと呼びます)、長さkごとに、配列内のすべての既存の長さに追加します (したがって、要素mが移入されている場合、 m + kに新しいエントリを作成します( m + k ≤ n の場合)。ただし、 mにある既存のエントリもそのままにしておきます) 。新しいセット。配列要素iでエントリのセットを構築して、合計iの長さブロックのリストのセットを表すことができます. 各セット エントリは、元の配列エントリにリンクする必要があります。これは、そこに到達した最後の長さを格納するだけで実行できます。これは、私が最近ここで回答した質問に似ています。必要に応じて重複を許可するように調整できます。
ただし、ギャップを考慮して上記のアプローチを変更する必要があります。各要素間の最小ギャップをx、最大ギャップをyと呼びましょう。長さkのエントリを追加するとき、それを別のエントリに追加するときは常に最小ギャップを含めます (したがって、mが入力されている場合、実際にはm + k + xでエントリを作成します)。要素間のギャップを含めるため、 kで初期エントリを作成し続けます。エントリを作成すると、それがスペースを埋めるかどうかも判断できます。新しいエントリにt個の要素が含まれ、合計がm であるとします。次に、m ≥ n - t ( y - x）。それがスペースを埋める場合は、ソリューション リストに追加する必要があります。必要な解の数に応じて、十分な解が見つかったらすぐにアルゴリズムを終了するか、すべての解を見つけるようにすることができます。最後に、ソリューション リストを反復処理します。
範囲内のものは、さまざまな方法のいずれかでギャップを表すことができますが、機能する 1 つの方法は、貪欲に「たるみ」を割り当てることです。たとえば、上記の例を使用して新しい全長から 1000 離れている場合は、最初の 3 つのギャップを 500 (それぞれ 300 の余分なスラック、合計 900 の追加) に選択し、4 つ目のギャップを 300 (余分な 100 のスラック、合計 1000) に選択し、すべての追加のギャップを最小 (200) にする必要があります。