java - reales - libro de android studio en español pdf

Encontrar el total combinado máximo en Java

Question

Supongamos que tiene un conjunto de números como a continuación:

[A,B,C]

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

Solo un número de cada conjunto Y de una categoría (A, B o C) puede usarse para encontrar la mayor suma. En este caso, A = 9, B = 6 y C = 6 producirán la mayor suma de 21. La mayor suma no puede ser 22 (9 + 7 + 6) porque los conflictos 9 y 7 son ambos categoría A.

¿Cómo puedo hacer esto en Java?

Tengo problemas para encontrar la suma más grande porque elegir el valor más grande en cada categoría no garantiza la suma más grande. Algunas categorías pueden forzarse en valores más pequeños que disminuyen la suma. Recuerde que solo se puede elegir un número de cada conjunto Y de una categoría.

Answer 1

Suena un poco como el Ocho Queens Puzzle , donde tienes que colocar 8 reinas en un tablero de ajedrez sin que ninguna de ellas esté en el camino de otra. (Si no conoces el ajedrez, no te preocupes por la analogía).

Supongamos que su matriz de ejemplo:

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

Encuentre el valor más grande en general (en este caso 9) y bloquee su columna y fila.

Su nueva matriz se ve así (con las x como opciones que ya no son válidas).

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

Repita ese proceso una y otra vez hasta que haya elegido un valor de cada columna y cada fila.

Ahora, como advertencia, tener varias ubicaciones para el máximo actual (como en el segundo paso del ejemplo, con los dos 6) conduce a algunas condiciones más. Dejaré parte de la diversión contigo, pero con mucho gusto te brindaré más ayuda si es necesario.

Advertencia

Esta respuesta no es válida, como lo señala Neil C. en los comentarios (contraejemplo específico:

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

Todavía no tengo la solución, pero quiero dejar esta respuesta disponible para ayudar a encontrar la solución correcta.

Answer 2

Aquí hay algunas ideas sobre cómo lo haría.

digamos que almacena sus datos en una matriz 2D de enteros

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

entonces, en este caso, las columnas son A, B, C, etc.

Necesitas iterar así al buscar el máximo:

data[i][fix] por lo que la columna se fija y la fila se cambia en el ciclo

en su ejemplo, si desea obtener el máximo de A y utiliza una matriz de 2d como lo aconsejé, entonces:

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

entonces el conjunto del que debe obtener el máximo para A es de data [0][0] , data[1][0] y data[2][0]

EDITAR:

Aquí hay una posible solución para ti.

//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);

Answer 3

Una manera fácil de buscar fuerza bruta es generar todas las permutaciones de longitud N donde N es el número de categorías. Luego, para cada permutación, calcule la suma de la Matrix[i][Permutation[i]] para todo i y tome el máximo.