スプリット等しい合計で3つのナンバーブロックに整数の配列

Question

が分からないのですが、私は、ここでそれを説明してみましょう：

だから、私は数字の配列、聞かせてのを持っています例えば1 2 3 4 5 6 7 8 9 10 11 14と言いますが、配列を3つの数値の配列に分割するアルゴリズムを書く必要があります。この場合は、等しくなります。

{14,2,4} {11,6,3} {10,1,9} {5,7,8} - 私はそれを得たと思います。

だから、私は私の頭の中で今持っていることは次のとおりです。

は、整数のあらゆる可能な合計の確認、および構造に3つの使用されるインデックスとの和を置きます。

次に、構造体の配列を使用して合計で並べ替え、N/3の合計数を検索し、見つかった場合はそのインデックスに従って数字を出力します。

アルゴリズムには、すべての数値を何度も実行することが含まれているため、速度が非常に遅くなります。誰かがより良いアルゴリズムを提案できますか？もし誰かがコードを書こうと思っていたら、私はCでプログラムでき、私はJavaを学び始めました。

ありがとうございました！

Answer 1

いつも12の数字で始めるつもりなら、あなたは言っていません。

あなたは数字の次の配列を有する：いない場合は数字の配列の数が3で割り切れなければならない1 2 3 4 5 6 7 8 9 10 11 14

1. 、ノーあります溶液。

2. 数値の配列を合計します。この場合、合計は80です。

3. 私たちは4つのグループを持っていますので、3の4つのグループがあります。合計を80/4または20のグループの数で割ります。この部門が ' tは整数を返しますが、解はありません。一度番号の配列、3つの数字を介し

4. 進み、一度、あなたが選択するために、1ゼロから始まる、12ビットのバイナリ整数を使用してインクリメントすることができる20の和トリプレットを保ちます三つ組バイナリ整数が3ビットの場合、それらのビットの位置を数字の配列のインデックスとして使用します。

5. トリプレットのグループ番号が存在するかどうかを確認し、配列内のすべての番号を使用するかどうかを確認します。そうであれば、あなたはあなたのソリューションを持っています。そうでない場合、解決策はありません。それは問題で与えられた数字の配列のための4つのソリューションがあることが判明：

   (2,4,14); (3,6,11); (1,9,10); (5,7,8) 
   (2,4,14); (1,8,11); (3,7,10); (5,6,9) 
   (1,5,14); (3,6,11); (2,8,10); (4,7,9) 
   (1,5,14); (2,7,11); (4,6,10); (3,8,9) 
   

   私はちょうどそれが生成するのにかかる時間の長さを表示するためのコードを書いて追加して編集

解決策。それは1秒未満で実行されました。

Answer 2

これは難しい問題です。コードを書くのが少し難しく、数が多いと解決するのに時間がかかるかもしれません。

まず解決策が可能かどうかを確認します。あなたは12の数字を持っています（11か13の場合は3のグループに入れられませんでした）ので、3の4つのグループが必要です。合計は80です。 〜20それぞれ。合計が79または78であれば動作しません。

数値を降順でソートします。最大の数はいくつかのグループになければならないので、それから始めましょう：14. 14は5,1または4,2と組み合わせることができます。両方の可能性をチェックします。

次に大きい数字はあるグループになければならないので、私たちは11をとります。これは8,1または7,2または6,3または5,4と組み合わせることができます。最初のグループが（14,5,1）の場合、2番目のグループは（11,7,2）または（11,6,3）になります。最初のグループが（14,4,2）の場合、2番目のグループは（11,8,1）または（11,6,3）になります。だからあなたの選択肢はあまり大きくならない。

したがって、毎回もう1つのグループを追加する再帰関数を書くことができます。追加する各グループには最大の残りの数と2つの数値が含まれるため、合計は20になります。すでに選択した番号を削除する必要があります。それは大まかな考えです。

Answer 3

（大まかなスケッチ）動的プログラミングのアプローチ：

3つの整数の配列を持っています。 intを使用済みとしてマークする方法があります。最初のマークのない番号を配列に追加し、使用済みとしてマークします。次のマークされていない数字を追加し、合計が目標合計よりもまだ下にあるかどうかを確認します（取得方法はわかっています）。それ以外の場合はもう一度試してください見つからない番号を見つけ、それを探します（マークが付いていないことを確認してください）。あなたがそれを見つけたとしよう。あなたはあなたのトリプレットを持っています（あなたはそれをどこかに保管しています、それは私がそれを簡単にするためにカバーしないメモパートです）。別の三つ組を探してください。

トリプレットにすべての番号が追加された後、次の番号が再帰的に検索されるので、元に戻って別の組み合わせを試すことができます。どのように動作するかは、ある時点で、トリプレットを構築せずに配列の最後に到達するかもしれないということです。次に、再帰呼び出しを返して、そこの他の番号を試してください。

すべての番号にマークを付けることができた場合にのみ実行されます。

ここでは改善の余地がありますが、動的プログラミングについて理解していれば、それを取得する必要があります。