8

私の質問は、CodeFuの練習問題（2012年ラウンド2問題3）についてです。基本的には、整数の配列を2つの（ほぼ）等しい半分に分割し、2つの間の可能な限り最小の差を返すことになります。以下に問題の説明を含めました。コメントに記載されているように、これは、動的計画法の分野での問題である、バランスの取れたパーティションの問題として説明できます。

現在、同様の問題が多く議論されていますが、この特定の問題に対する効率的な解決策を見つけることができませんでした。もちろん、問題は、トラバースできる組み合わせの数がすぐに大きくなりすぎて、ブルートフォース検索を実行できないことです（少なくとも再帰を使用する場合）。最大の問題セットを除くすべての問題に対して正常に機能する再帰的なソリューションがあります。再帰を早期に停止する最適化をいくつか追加しようとしましたが、パフォーマンスが遅すぎて、CodeFuで許可されている最大5秒以内の最大長（30）の配列を解決できません。コードを改善または書き直す方法についての提案は大歓迎です。また、反復バージョンを作成するのに役立つかどうかも知りたいです。

更新：このすばらしいサイトでは、バランスの取れたパーティションの問題について理論的な議論があり、動的な方法でこれを実行して解決する方法についての良いアイデアが得られます。それが私が求めていることですが、理論を正確に実践する方法がわかりません。映画では、2つのサブコレクションの要素が「バックポインターの古いトリックを使用して」見つけることができると述べていますが、その方法がわかりません。

問題

あなたとあなたの友人は、さまざまな量のコインをたくさん持っています。コインを2つのグループに分けて、それらのグループ間の違いを最小限に抑える必要があります。

たとえば、サイズが1,1,1,3,5,10,18のコインは、次のように分割できます：1,1,1,3,5および10,181,1,1,3,5,10および18または1 、1,3,5,10および1,18 3番目の組み合わせは、グループ間の差が1しかないため、有利です。制約：コインの要素は2〜30で、コインの各要素は1〜1です。 100000を含む

戻り値：コインを2つのグループに分割した場合に可能な最小の差

注：CodeFuのルールでは、CodeFuのサーバーでの実行時間は5秒以内であると規定されています。

メインコード

Arrays.sort(coins);

lower = Arrays.copyOfRange(coins, 0,coins.length-1);
//(after sorting) put the largest element in upper
upper = Arrays.copyOfRange(coins, coins.length-1,coins.length);            

smallestDifference = Math.abs(arraySum(upper) - arraySum(lower));
return findSmallestDifference(lower, upper, arraySum(lower), arraySum(upper), smallestDifference);

再帰コード

private int findSmallestDifference (int[] lower, int[] upper, int lowerSum, int upperSum, int smallestDifference) {
    int[] newUpper = null, newLower = null;
    int currentDifference = Math.abs(upperSum-lowerSum);
    if (currentDifference < smallestDifference) {
        smallestDifference = currentDifference;
    } 
    if (lowerSum < upperSum || lower.length < upper.length || lower[0] > currentDifference 
            || lower[lower.length-1] > currentDifference 
            || lower[lower.length-1] < upper[0]/lower.length) {
        return smallestDifference;
    }
    for (int i = lower.length-1; i >= 0 && smallestDifference > 0; i--) {           
       newUpper = addElement(upper, lower[i]);
       newLower = removeElementAt(lower, i);
       smallestDifference = findSmallestDifference(newLower, newUpper, 
               lowerSum - lower[i], upperSum + lower [i], smallestDifference);
    }
    return smallestDifference;
}

データセット

これは、解決に時間がかかりすぎるセットの例です。

{100000,60000,60000,60000,60000,60000,60000,60000,60000、60000,60000,60000,60000,60000,60000,60000,60000,60000、60000,60000,60000,60000,60000,60000,60000 、60000,60000、60000,60000,60000}

ソースコード全体が必要な場合は、Ideoneに配置しました。

4

2 に答える 2

3

明確にするために編集 ：質問で5秒未満で実行するという追加の制限が指定される前に、この回答を書きました。また、そうではないように見えても、ブルートフォースが発生する可能性があることを示すために作成しました。したがって、この答えは、この問題に対する「最良の」答えを意味するものではありません。正確には、力ずくの解決策を意味します。副次的な利点として、この小さなソリューションは、「大きな」アレイに対する答えが正しいことを許容可能な時間内に検証するために、別のソリューションを作成する人を助ける可能性があります。

もちろん、問題は、トラバースできる組み合わせの数がすぐに大きくなりすぎて、力ずくの検索ができないことです。

最初に述べた問題（最大実行時間5秒が指定される前）を考えると、私はそのステートメントに完全に異議を唱えます;）

あなたは特に最大長が30であると書きました。

私は他の解決策について話しているのではないことに注意してください（たとえば、制約が与えられた場合に機能する場合と機能しない場合がある動的計画法の解決策など）。

私が言っているのは、2 30は大きくないということです。それは、10億を少し超える程度であり、それだけです。

最新のCPUは、1つのコアで1秒あたり数十億サイクルを実行できます。

これを解決するために再帰する必要はありません。再帰するとスタックが破壊されます。考えられるすべての左/右の組み合わせを決定する簡単な方法があります。0から2exp30-1までカウントし、すべてのビットをチェックします（たとえば、ビットオンは値を左に置くことを意味し、オフは値を置くことを意味します）右の値）。

したがって、問題の説明が間違っていなければ、最適化なしで次のアプローチが機能するはずです。

  public static void bruteForce( final int[] vals) {
    final int n = vals.length;
    final int pow = (int) Math.pow(2, n);
    int min = Integer.MAX_VALUE;
    int val = 0;
    for (int i = pow -1; i >= 0; i--) {
        int diff = 0;
        for ( int j = 0; j < n; j++ ) {
            diff += (i & (1<<j)) == 0 ? vals[j] : -vals[j];

        }
        if ( Math.abs(diff) < min ) {
            min = Math.abs(diff);
            val = i;
        }
    }

    // Some eye-candy now...
    for ( int i = 0 ; i < 2 ; i ++ ) {
        System.out.print( i == 0 ? "Left:" : "Right:");
        for (int j = 0; j < n; j++) {
            System.out.print(((val & (1 << j)) == (i == 0 ? 0 : (1<<j)) ? " " + vals[j] : ""));
        }
        System.out.println();
    }
}

例えば：

bruteForce( new int[] {2,14,19,25,79,86,88,100});
Left: 2 14 25 79 86
Right: 19 88 100


bruteForce( new int[] {20,19,10,9,8,5,4,3});
Left: 20 19
Right: 10 9 8 5 4 3

30個の要素の配列では、私の安価なCPUでは125秒で実行されます。これは、単一のコアで実行される「最初のドラフト」で完全に最適化されていないソリューションの場合です（前述の問題は並列化するのが簡単です）。

もちろん、より洗練されたものを取得して、多くの中間結果を再利用できるため、125秒未満で30個の要素の配列を解くことができます。

于 2012-10-31T13:32:59.073 に答える
2

は、すべてのコインNの合計です。コインの合計が に最も近いコインのサブセットを見つける必要がありますN/2。考えられるすべての合計を計算して、最適なものを選択しましょう。最悪の場合、2^30 の可能な合計が期待されるかもしれませんが、可能な最大の合計は 100K*30、つまり 3M であり、約 1G になる 2^30 よりもはるかに小さいため、これは発生しない可能性があります。したがって、可能なすべての合計を保持するには、3M int または 3M ビットの配列で十分なはずです。

したがって、配列がaあり、合計が可能なa[m] == 1場合のみです。m

ゼロ化された配列から開始しa[0]=1、合計0が可能であるため (1 つはコインを持たない) を持っています。

for (every coin)
  for (int j=0; j<=3000000; j++)
    if (a[j] != 0)
      // j is a possible sum so far
      new_possible_sum = j + this_coin
      a[new_possible_sum] = 1

30 * 3M ステップで終了すると、考えられるすべての合計がわかります。mに最も近い数を見つけますN/2。あなたの結果はabs(N-m - m)です。時間と記憶の境界に収まることを願っています。

編集：修正が必要であり、2つの最適化が必要です：

  1. 配列を降順でウォークします。そうしないと、1 ドル硬貨が配列全体を一度に上書きしてしまいます。
  2. 配列のサイズを (0 を含む) に制限して、N+1小さなコイン セットをより速く解決します。
  3. ほとんどの場合、 と の 2 つの同一の結果が得られるため、配列サイズを に減らしmます。の境界チェックを追加します。より大きな可能性のある金額を捨てます。N-mN/2new_possible_sum
于 2012-10-31T18:09:39.890 に答える