5

以下のような一連の数値があるとします。

[A,B,C]

[6, 4.5, 6]
[7, 6, 5]
[9, 4.5, 6]

カテゴリ (A、B、または C) の各セットANDから 1 つの数値のみを使用して、最大合計を見つけることができます。この場合、A=9、B=6、および C=6 は 21 の最大の合計を生成します。9 と 7 はどちらもカテゴリ A であるため競合するため、最大の合計は 22 (9+7+6) になることはありません。

Javaでこれを行うにはどうすればよいですか?

各カテゴリで最大の値を選択しても最大の合計が得られるとは限らないため、最大の合計を見つけるのに苦労しています。一部のカテゴリは、合計を減らすより小さな値に強制される場合があります。カテゴリの各セットから 1 つの番号のみを選択できることに注意してください。

4

3 に答える 3

1

エイト クイーンズ パズルに少し似ているように聞こえますが、チェス盤に 8 つのクイーンを配置する必要があります。(チェスを知らなくても、類推を心配する必要はありません)。

あなたの例の配列を考えてみましょう：

[6, 4.5, 6]
[7,   6, 5]
[9, 4.5, 6]

全体で最大の値 (この場合は 9) を見つけ、その列と行をブロックします。

新しい配列は次のようになります (x の選択肢は無効になります)。

[x, 4.5, 6]
[x,   6, 5]
[x,   x, x]

各列と各行から 1 つの値を選択するまで、このプロセスを繰り返します。

ここで、警告として、現在の最大値に複数の場所がある (例の 2 番目のステップのように、2 つの 6 がある) と、さらにいくつかの条件が発生します。楽しみの一部は残しておきますが、必要な場合は喜んでお手伝いします。

警告

コメントで Neil C. が指摘したように、この回答は有効ではありません。具体的な反例:

[10, 9, 1]
[ 9, 1, 1]
[ 1, 1, 1]

私はまだ修正を手元に置いていませんが、正しい解決策を考え出すのに役立つように、この回答を残しておきたいと思います.

于 2012-08-08T20:33:06.323 に答える
0

ブルート フォース検索の簡単な方法の 1 つは、長さ N の順列をすべて生成することです。ここで、N はカテゴリの数です。次に、順列ごとにMatrix[i][Permutation[i]]、すべての i の合計を計算し、最大値を取ります。

于 2012-08-09T03:02:25.107 に答える
-2

これが私がそれを行う方法についてのいくつかのアイデアです。

データを整数の2次元配列に保存するとしましょう

int [] [] data = new int [rows] [columns]

したがって、この場合、列は A、B、C などです。

最大値を検索するときは、次のように繰り返す必要があります。

data[i][fix]そのため、列は固定され、行はループで変更されます

あなたの例では、最大値を取得したい場合、A私がアドバイスしたように2次元配列を使用すると、次のようになります。

int [] [] data = new int [3][3];

A次に、 fromの最大値を取得する必要があるセットはdata [0][0]でdata[1][0]あり、data[2][0]

編集：

ここに考えられる解決策の 1 つがあります。

//here is our data array.
int [][] data = new int[3][];

//fill up with som random data
data[0] = new int[]{10,20,4,5,56,87,9};
data[1] = new int[]{1,65,0,10,3};
data[2] = new int[]{34,5,6,67,3,54};

//get the biggest arrays length
int maxArrayLength = 0;
for(int i=1; i<data.length; i++)
{
    if(data[i].length > data[maxArrayLength].length)
        maxArrayLength = i;
}
maxArrayLength = data[maxArrayLength].length;

//collect the max in each category
int [] categoryMax = new int[maxArrayLength];

//loop through the categories
for(int i=0; i<maxArrayLength; i++)
{
    //in each iteration we get a winner
    int categoryWinner = 0;

    // now loop through the values of the current category
    for(int j=0; j<data.length; j++)
    {
        int [] actualArray = data[j];
        int [] winnerArray = data[categoryWinner];

        //check if we are in the bounds, if so, then perform a simple maxsearch
        if(i<actualArray.length)
            if(actualArray[i] > winnerArray[i])
            categoryWinner = j;
    }

    //set the current element of the winners array.
    categoryMax [i] = data[categoryWinner][i];
}

int sum = 0;

// we are ready, print it out!
for(int i=0; i<categoryMax.length; i++)
{
    System.out.println((i+1) + ". groups winner: " + categoryMax[i]);
    sum+=categoryMax[i];
}
System.out.println(sum);
于 2012-08-08T12:05:32.570 に答える