algorithm - サブセット内の最大要素数を持つナップサック

Question

私は整数配列を持っており、W に等しい最大 3 つの要素を持つこの配列のサブセットを見つける必要があります。

ナップザックを使用してこの問題を解決できますか? または、配列の 1-2-3 要素の組み合わせごとに計算する必要がありますか?

もうありがとう

Answer 1

合計が になる3 つの要素を探すにWは、これがまさに3SUM 問題です。

次のいずれかにより、O(n ² ) 時間で解決できます。

• a各数値をハッシュ テーブルに挿入し、2 つの数値との組み合わせごとに、ハッシュ テーブルに存在bするかどうかを確認W-a-bします。

• 配列を並べ替えてから、要素ごとに、両側から 2 つの反復子を使用しaて合計する 2 つの要素を探します。W-a

整数の範囲が の範囲内にある場合[-u, u]、O(n + u log u) の高速フーリエ変換を使用して問題を解決できます。これまたは上記のアプローチのいずれかの詳細については、上記のリンクを参照してください。

あなたの問題は、よく知られた問題である 3SUM の解決に依存しているため、上記の 3SUM のよく知られた解決策よりも実行時間の長い解決策を見つけることはほとんどありません。

1 つの要素を探すには:

単純な線形検索 (O(n)) を実行できます。

2 つの要素を探すには:

^{これは、O(n 2} )の 2 つの要素の各組み合わせをチェックするだけで解決できます(3 つの要素の漸近的な実行時間は O(n ² ) の合計時間になるため、より複雑なことを行う必要はありません。は）。

また、上記の 3SUM と同じ方法を使用して、O(n) または O(n log n) で解くこともできます。

全体の実行時間:

O(n ² ) または O(n + u log u) (3SUM 部分を解くために使用された方法に応じて)。