algorithm - 整数の除算

Question

以下で説明するアルゴリズムの問​​題の解決策に問題があります。

整数のセット (配列など) があります。私たちの仕事は、合計が互いに等しいグループにそれらを分割することです (要素の数が同じである必要はありません)。原始集合が分割できない場合、「分割できない」と答えなければなりません。

例: セットAが与えられ[-7 3 3 1 2 5 14]ます。答えは[-7 14], [3 3 1], [2 5]です。

確かにそれが不可能な場合を言うのは簡単なようです。主集合の合計が 3 で割り切れない場合: sum(A) % 3 != 0.

その問題を解決する方法はありますか？

Answer 1

これは、分割問題の3 分割問題の変種です。違いは、従来の分割問題では、合計が互いに等しい 2 つのセット (3 つではなく) に分割されることです。この問題は NP 完全であるため、多項式時間の解を見つけることはほとんどありません。2 分割問題には疑似多項式時間解がありますが、3 分割問題にはありません。

2 パーティション アルゴリズムを 3 パーティション アルゴリズムに適応させる方法の概要については、この回答を参照してください。並列ソリューションについては、このペーパーも参照してください。