3

長さ n の配列 x と、S 内の各配列の長さが n であるような配列 S のセットが与えられた場合、すべての 1 <= i <= n に対して x[i] となる S 内の配列 G の最大サイズのセットを見つけます。 >= sum(g[i]) G のすべての g。

ex x = [3, 3] かつ S = {[3, 0], [1, 1], [2, 1]} の場合、最適なセットは {[1, 1], [2, 1]} です。合計は [3, 2] であり、各インデックスの要素は x の対応する要素より小さいためです。{[3, 0], [1, 1]} は、合計が [4, 1] であり、4 > x[0] = 3 であるため機能しません。

実行時間が n と |S| の多項式になるアルゴリズムはありますか?

背景/コンテキスト: この質問は、スクラブルに関する質問から生じました。タイルのリストと単語が与えられたら、タイルで単語を作成できますか? 与えられたタイルのリストと単語のリストに拡張しました。タイルから形成できるリスト内の単語の最大数はいくつですか?

4

1 に答える 1

3

これが多次元ナップザック問題です。

nと の両方に多項式時間のアルゴリズムがないことを証明するには|S|(またはこれが強力な NP 困難な問題であることを証明するには)、この問題を単純化して1、 arrayxと values0またはarray の値のみを許可1しますS。この単純化の後、古典的な NP 完全問題であるSetpackingの最適化バージョンが正確に得られます。

セット パッキング問題との関係は、適切な近似アルゴリズムも存在しないことを示唆しています。

これにより、アルゴリズムの選択肢がかなり制限されます。

  1. 分枝縛り。
  2. 整数線形計画法。
  3. シミュレーテッド アニーリングやタブー検索などのメタヒューリスティック アルゴリズム。
于 2012-10-17T22:14:12.183 に答える