0

次の問題があります: N 個の整数のセットが与えられた場合、それらを 2 つのほぼ等しいパーティションに分割し、より大きなパーティションの合計が最小になるようにします。これは、1 つの例外を除いて、従来のパーティションの問題とほぼ同じように思えます。

例: N = 4 数値: 20 5 3 1

結果: 15

説明: 最初の数値は 2 で除算され、各半分は 2 つのパーティションのいずれかに配置されます => 最初のパーティション = 10、2 番目のパーティション = 10。2 番目の数値は最初のパーティションに追加されます => 最初のパーティション = 15。最後の 2 つの数字が 2 番目のパーティションに追加されます => 2 番目のパーティション = 14

=> より大きいパーティション (パーティション 1) の合計 = 15。

私が持っているアイデアは、奇数を減らして並べ替え、貪欲なアルゴリズムを使用してそれらを追加し始め、常に2つのパーティションの合計の差を可能な限り最適に保つことです。奇数の処理が終わったら、残っているのは偶数を取り、1 つのパーティションにそれらを完全に追加する方が、それらを 2 で割って 2 つのパーティションの 1 つに追加するよりも最適かどうかを確認することです。

また、次のデータセットについても、アルゴリズムは正しい答えを提供します: N = 2 数字: 16 15

=> 15 を取り、それを最初のパーティションに追加し、次に 16 を取り、それを 2 で割るのが最適ではないことを確認します。したがって、2 番目のパーティションに追加します。

=> 答えは 16 になります。

アルゴリズムが最適な答えを提供しない一連のデータを提供していただければ幸いです。また、改善点を提案していただければ幸いです。

ありがとう！:)

4

3 に答える 3

3

すべての偶数を 1 回のパスで分割し、従来の分割アルゴリズムを適用します。または、分割数を最小限に抑えるための二次的な目的はありますか?

于 2011-04-07T18:25:25.737 に答える
1

分割問題はNP完全です。つまり、多項式時間アルゴリズムが存在する可能性は低いです。変更されたバリアントもNP完全です。元のバージョンへの縮小は非常に簡単です。

于 2011-04-07T19:05:42.297 に答える
0

すべての数字を半分に分割し、奇数の余分な 1 をサイクリング パーティションに入れてみませんか? 2 番目のパーティションの合計は常に小さくなります。

リスト: 20 17 6 5 3 0 -1 9999999



P1: 10 | 8+1 | 3 | 2 | 1+1 | 0 | -1 | 4999999+1 | ==> 合計は 5000025 です
P2: 10 | 8 | 3 | 2+1 | 1 | 0 | -1+1 | 4999999 | ==> 合計は 5000024 です

于 2011-04-07T18:33:00.977 に答える