Ayuda para resolver un algoritmo en Java (combinaciones posibles)

[xNacht.Engelx]

Hola a todos, estoy intentando resolver un algoritmo en Java, nunca había programado en Java y estoy algo atorada con este problema, dice:

Se tienen "s" cantidad de barras de "x" longitud a las cuales se harán "m" cantidad de cortes de "y" longitud, obtener el residuo de los cortes, además las posibles combinaciones  de corte y calificarlas (cuál es la mejor/más óptima).

Hasta ahorita tengo un código que supuestamente pone las posibles combinaciones, pero al momento de ejecutarlo después de las primeras combinaciones en las demás no aparecen todos los cortes, y estoy pensando en cómo puedo hacer para calificarlas, ¿alguna idea? Gracias

CÓDIGO:
   

Código: [Seleccionar]

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int s, n=0, cont=1, m, i, j, q, a, z;
   
    System.out.print("Numero de barras de las que se obtendran las piezas : ");
    s = scan.nextInt();
    int b[] = new int[s];
   
    do{
        System.out.print("Longitud de la barra " + cont + ": ");
        b[n] = scan.nextInt();
        n++;
        cont++;
    }while (n<s);
 
    System.out.print("Numero de piezas por cortar: ");
        m = scan.nextInt();
        int p[] = new int[m]; //Se designa el numero de piezas a cortar
       
        n=0;
        cont=1;
       
        do{
            System.out.print("Longitud de la pieza " + cont + ": ");
            p[n] = scan.nextInt();
            n++;
            cont++;
        }while (n<m); //controla cuantas longitudes de piezas se van ingresando
       
        int barras[][] = new int[s][s];  //se crean los arreglos bidimensionales para combinaciones
        int piezas[][] = new int[m][m];  //de tamaño de las barras y de las piezas
       
      //PASA EL ARREGLO DE BARRAS AL ARREGLO BIDIMENSIONAL DE BARRAS
        for (n=0; n<s; n++){   //n<num de barras
            q=n;         
            for (cont=0; cont<s; cont++){ //cont< num de barras
                barras[n][q] = b[cont];    //se ingresa en la posicion {n}{q} del bidimensional barras lo que hay en barras{cont}
                q++;
                if (q>=s){     //si control de ingreso de barras es mayor o igual al num de barras
                    q = q - s;      //se resta el control de ingr.barras menos el num de barras
                }
            }
        }
       
       //PASA DEL ARREGLO DE PIEZAS A BIDIMENSIONAL DE PIEZAS       
        for (n=0; n<m; n++){
            q=n;
            for (cont=0; cont<m; cont++){
                piezas[n][q] = p[cont];
                q++;
                if (q>=m){
                    q = q - m;                   
                }
            }
        }
        //SE CREAN ARREGLOS AUXILIARES DE BARRAS Y PIEZAS DE TAMAÑO DEL # DE PIEZAS Y BARRAS
        int auxb[][] = new int[s][s];
        int auxp[][] = new int[m][m];
        int cpb[][]= new int [100][100];  //Almacenará los cortes por pieza
       
        for (i=0; i<s; i++){
            for (j=0; j<m; j++){
               
                for(q=0; q<s; q++){     //pasa lo que hay en el arreglo de barras a auxiliar de barras
                    auxb[i][q] = barras[i][q];
                }
                       
                for(q=0; q<m; q++){     //pasa lo que hay en el arreglo de piezas a auxiliar de piezas
                    auxp[j][q] = piezas[j][q];
                }
               
                q=0;   //restaura en cero a "q"
                for (n=0;n<s;n++){   //cuando n sea menor que la cantidad de barras
                    for (cont=0;cont<m;cont++){  //cuando cont sea menor que la cantidad de cortes
                        if (barras[i][n]>=piezas[j][cont] && piezas[j][cont]!=0){
                            barras[i][n] = (barras[i][n] - piezas[j][cont]);
                            cpb[n][q]=piezas[j][cont]; //guarda el valor de la pieza que se restó o corto
                            piezas[j][cont]=0; //ese lugar se iguala a cero
                            q++;
                            }
                        }
                    }
               
                q=0;
                while(q<m && piezas[j][q]==0){
                    q++;
                }
               
                if (q==m){
                    a=1;
                    z=0;
                    System.out.print("Probabilidad " + i + "," + j + " \n");
                    for (q=0; q<s; q++){
                        System.out.print("El valor del residuo de la barra " + a + " es: " + barras[i][q] + ", con cortes de ");
                        while (cpb[q][z]!=0){
                            System.out.print(cpb[q][z] + ", ");
                            z++;
                        }
                        System.out.print("\n");
                        a++;
                        }
                    System.out.print("\n");
                }
               
                else
                    System.out.print("No se pueden realizar los cortes con las barras dadas \n");
               
                for(q=0; q<s; q++){
                    barras[i][q] = auxb[i][q];
                }
               
                for(q=0; q<m; q++){
                    piezas[j][q] = auxp[j][q];
                }
               
            }
        }
             
    }

[Alex Rodríguez]

Pues parece un problema más complicado de lo que pueda parecer a primera vista. Se trata de una optimización, ya que tienes que encontrar la mejor solución o solución óptima (se supone que será aquella para la que se obtienen los cortes usando el menor número de barras posible), pero además te piden todas las posibles combinaciones de corte, lo cual obliga a generar todas las posibles combinaciones aunque se sepa que no van a ser óptimas.

Lo primero que habría que aclarar es el enunciado del problema: cuando se dice "s" cantidad de barras de "x" longitud podríamos pensar que s es un número variable y x un número fijo. Por ejemplo podríamos pensar que fueran 5 barras de 2 metros de longitud.

O podríamos pensar que s es un número variable y x un número variable también, por ejemplo 5 barras con longitudes 3, 2, 4, 3, y 1 metro.

Con los cortes sucede lo mismo: podríamos pensar que todos los cortes son iguales. Por ejemplo 3 cortes de 1 metro, o bien que cada corte tiene su propia longitud.

Lo que veo es que has supuesto que las barras son de longitud variable y los cortes son de longitud variable.

Supongamos que tenemos 2 barras una de 3 metros y otra de 4 metros y que hay que generar 2 cortes uno de 1 metro y otro de 2 metros. Tendríamos que generar un árbol de soluciones donde una primera ramificación es el número de barras que intervienen en la solución. Para cada una de estas ramificaciones tendríamos que buscar las diferentes asignaciones de corte a cada barra posibles y calcular su puntuación.

Por ejemplo teniendo dos barras tendríamos dos ramificaciones: hacia un lado, una solución donde solo interviene una barra, y hacia otro lado una solución donde intervienen dos barras.

En la solución donde solo interviene una barra tendríamos tantas ramificaciones como barras, en nuestro caso 2, lo que nos llevaría a asignar todos los cortes a la primera barra y esto nos da la SOLUCIÓN 1: barra 1 con 2 cortes, residuo 0; Por otro lado si asignamos todos los cortes a la segunda barra tenemos la SOLUCIÓN 2: barra 2 con 2 cortes, residuo 1.

En la solución donde intervienen dos barras tendríamos tantas ramificaciones como posibles combinaciones de barras dos a dos. Si tuviéramos 4 barras las ramificaciones serían 1-2, 1-3, 1-4, 2-3, 2-4, 3-4. Seguidamente tendríamos tantas ramificaciones como posibles combinaciones de asignaciones de cortes a las barras.

En el ejemplo anterior sólo tenemos dos barras por lo que la única ramificación sería 1-2, y las posibles combinaciones serían:

a) Asignar el primer corte a la primera barra (residuo: 2) y el segundo a la segunda barra (residuo: 2) con residuo total 4, SOLUCIÓN 3

b) Asignar el primer corte a la segunda barra (residuo: 3) y el segundo a la primera barra (residuo: 1) con residuo total 4, SOLUCIÓN 4

En nuestro caso no tenemos más combinaciones posibles, la calificación de las combinaciones la haríamos en base al residuo que dejan, con lo cual la calificación sería:

SOLUCIÓN 1: 0
SOLUCIÓN 2: 1
SOLUCIÓN 3: 4
SOLUCIÓN 4: 4

Y la solución óptima sería la solución 1 porque es la que genera el menor residuo.

En algunos casos no habría una sola solución óptima, sino varias soluciones óptimas (que empatarían con la mejor puntuación). Al aumentar el número de barras y de cortes la cantidad de combinaciones crecería desmesuradamente.


Quizás haya una solución más sencilla, pero a simple vista parece un problema de algoritmia avanzada a resolver con la técnica de "Backtracking" y el primer paso a dar sería generar todas las posibles combinaciones (todas las posibles cantidades de barras, y todas las posibles combinaciones de cortes para cada cantidad). Esto se suele hacer mediante algoritmos recursivos, pero no sé si has trabajado con algoritmia recursiva. Esta es bastante complicada de entender y plantear si no se ha trabajado con ella.

En resumen, lo veo complejo si el enunciado es tal como se ha supuesto. Normalmente en los enunciados se introducen simplificaciones que facilitan la resolución del problema, pero habría que ver si el enunciado es simplificable respecto a lo supuesto. También es posible que haya una forma más sencilla de resolverlo, pero a mí no se me ocurre. Saludos.