与えられたのは要素のセットです。個々のグループの要素の合計の差が最小になるように、それらを2つのグループに分割する必要があります。
例：
5
4 6 7 2 1
2つのグループは：{4,6}と{7,2,1}です。
私のアプローチ：この問題の強引な解決策にしか遭遇していません。つまり、(2^n)ビットシフト手法を使用してセットのすべてのサブセットを生成します。
より良い解決策を探しています。
1149 次
1 に答える
2
あなたに解決策を与える代わりに、私はあなたに2つのヒントを与えます：
元の問題を解く代わりに、すべての要素の合計を計算します。これを示し
Sます。次のように述べられている問題を解決します-合計が。以下である与えられた数のサブセットを見つけますS/2。残りの数は他のサブセットを形成します。上で説明した問題は、すべての要素のコストが等しい非常に単純化されたナップサック問題です。ここでも、動的計画法を使用して解決できます（ただし、この場合、古典的なナップサック問題に使用されるものよりもはるかに簡単になります）
于 2013-03-05T07:30:39.127 に答える