0

サイズが 2^N で、N = 25 の 4 つの配列があります。配列の要素は、私のアルゴリズムによって生成されています。これらはソートされていますが、数字が含まれています。ここで、array1 の各要素を取得し、array2、array3、array4 の要素を選択して、それらの合計が最小になるようにする必要があります (合計と言うと、a1[k] +-a2[j]+-a3[m] を取ることができます)。 +-a4[t]. K 次元のマージ問題に似ていると思います. 同じことを行うための文献/実装/ヒューリスティックを指摘できますか. よろしく, アッラーバクシュ

4

2 に答える 2

0

この問題はO(n)で解決できると思います。和集合のすべての配列をマージして、2番目の値が配列番号になるようにします。それを繰り返し、各反復フォームで4つの値から回答し、各ステップで選択した数値間の最大距離を計算します->この値を最小化します。
各配列から最小数の結果配列を初期化します。

public Integer[] findClosest(int[][] unionSet, Integer[] result) {

    for (int i = 0; i < unionSet.length; i++) {
        int value = unionSet[i][0];
        int position = unionSet[i][1];
        int currentDistance = getDistance(result);
        Integer[] temp = Arrays.copyOf(result, result.length);
        temp[position] = value;
        int newDistance = getDistance(temp);
        if (newDistance <= currentDistance) {
            result = temp;
        }
    }
    return result;
}

private int getDistance(Integer[] result) {
    int max = 0;
    int min = 0;
    for (int i = 1; i < result.length; i++) {
        if (result[i] != null) {
            if (result[i] > result[max]) {
                max = i;
            }
            if (result[min] != null && result[i] < result[min]) {
                min = i;
            }
        }
    }

    return Math.abs(result[max] - result[min]);
}
于 2012-08-21T18:28:14.793 に答える
0

ステップ 1 array1[k] については、array2、array3、または array4 で法が array1[k] に近づくような数値を見つけます。

eg . 
array1 = {1, 3, 67}
array2 = {-31, 7, 47}
array3 = {-1, 2, 10}
array4 = {14, 15, 66}

For array1[0] (ie. 1), the number closest to it is in array3 and its -1 as mod(-1) = 1

ステップ 2 次に、残りの 2 つの配列から、互いに近い数値のペアを見つけます。(再びモジュラスを考慮してください)

eg . 
array2 = {-31, 7, 47}
array4 = {14, 15, 66}

Closest elements are 7 and 14 with -7 + 14 = 7.

最終的に、4 つの配列すべてから min(a1[k] +-a2[j]+-a3[m]+-a4[t]) を取得します。

于 2012-04-04T06:43:57.980 に答える