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