5

假设您有一组如下数字：

[A,B,C]

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

一个类别（A、B 或 C）的每个集合AND中只能使用一个数字来找到最大和。在这种情况下，A=9、B=6 和 C=6 将产生 21 的最大和。最大和不能是 22 (9+7+6)，因为 9 和 7 由于都是 A 类而发生冲突。

我怎样才能在 Java 中做到这一点？

我很难找到最大的总和，因为在每个类别中选择最大值并不能保证最大的总和。某些类别可能会被强制为较小的值，从而减少总和。请记住，只能从类别的每一组 AND 中选择一个数字。

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]

一遍又一遍地重复该过程，直到您从每一列和每一行中选择一个值。

现在，作为警告，当前最大值有多个位置（如示例的第二步，两个 6）会导致更多情况。我会把一些乐趣留给你，但如果需要，我很乐意提供更多帮助。

警告

正如 Neil C. 在评论中指出的那样，这个答案是无效的。具体反例：

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

我手头还没有修复程序，但我想留下这个答案，以帮助提出正确的解决方案。

于 2012-08-08T20:33:06.323 回答
0

蛮力搜索的一种简单方法是生成长度为 N 的所有排列，其中 N 是类别的数量。然后，对于每个排列，计算Matrix[i][Permutation[i]]所有 i 的总和并取最大值。

于 2012-08-09T03:02:25.107 回答
-2

这里有一些关于我将如何做的想法。

假设您将数据存储在二维整数数组中

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

所以在这种情况下，列是 A、B、C 等。

搜索最大值时需要像这样迭代：

data[i][fix]所以列是固定的，行在循环中改变

在您的示例中，如果您想获得最大值，A并且像我建议的那样使用二维数组，那么：

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

那么你需要从中获得最大值的集合A是data [0][0]，data[1][0]并且data[2][0]

编辑：

这是适合您的一种可能的解决方案。

//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 回答