Java - programación dinamica

 
Vista:
sin imagen de perfil

programación dinamica

Publicado por Carlos Guzman (1 intervención) el 26/11/2017 04:47:10
Buenas noches... disculpen la molestia sin embargo intente realizar este ejercicio para la U, no se si alguien me pueda orientar un poco sobre la solucion del siguiente problema.... le agradeceria encontre algunos ejemplos pero la verdad no logro encontrar una solución

PROBLEMA: Sobre un río hay n embarcaderos. En cada uno de ellos se puede alquilar un bote que permite ir a cualquier otro embarcadero río abajo (es imposible ir río arriba). Existe una tabla de tarifas que indica el coste del viaje del embarcadero i al j para cualquier embarcadero de partida i y cualquier embarcadero de llegada j más abajo en el río (i < j). Puede suceder que un viaje de i a j sea más caro que una sucesión de viajes más cortos, en cuyo caso se tomaría un primer bote hasta un embarcadero k y un segundo bote para continuar a partir de k. No hay coste adicional por cambiar de bote.
Diseñe un algoritmo basado en una estrategia de programación dinámica que determine el coste mínimo para ir de un punto i a un punto j. El usuario podrá cargar el número de embarcaderos y los diferentes costes en una tabla, así como también el embarcadero de partida y el de llegada, y el algoritmo dará como respuesta qué embarcaderos incluirá la ruta y cuál es su costo.

CODIGO ACTUAL QUE TENGO EN JAVA

package Ejercicio2Final;

import java.util.Scanner;

public class dinamismo {

public static void main(String[] args) {
// TODO Auto-generated method stub
int embarcadero, origen, destino, maximo=0;
Scanner entrada = new Scanner(System.in);
System.out.println("Escriba el total de embarcaderos, el valor de barcos sera igual al de embarcaderos");
embarcadero = entrada.nextInt();

int costo[][]= new int[embarcadero][embarcadero];;

for(int i = 0;i < costo.length; i++){
for(int j = 0;j < costo[i].length; j++){
System.out.println("Escriba el valor del bote #"+(i+1)+" embarcadero #"+(j+1));
costo[i][j] = entrada.nextInt();
}
}


System.out.println("Matriz de costo");


mostrarMatriz(costo);


do {
System.out.println("Escriba el origen del barco");
origen = entrada.nextInt();
if(origen>embarcadero ||origen<0) {
System.out.println("El origen no puede ser menor a 0 o superior a "+embarcadero);
}
}
while(origen>embarcadero ||origen<0);


do {
System.out.println("Escriba el destino del barco");
destino = entrada.nextInt();
if(destino>embarcadero ||destino<0) {
System.out.println("El destino no puede ser menor a 0 o superior a "+embarcadero);
}
}
while(destino>embarcadero ||destino<0);

int matriz[][]=new int[embarcadero][embarcadero];

System.out.println("Resultado Final");
System.out.println(embarcaderos(origen, destino, costo.length, costo));

}

//Metodo mostrar matriz
static void mostrarMatriz(int matriz[][]) {
for(int i = 0;i < matriz.length; i++){

System.out.print("bote "+i+"|");

for(int j = 0;j < matriz[i].length; j++){
System.out.print(matriz[i][j]);
if (j!=matriz[i].length-1) {
System.out.print("\t");
}
}
System.out.print("|");
System.out.print("\n");
}

System.out.print("---------------------------------------------------------");
System.out.print("\n");
}

//Funcion de embarcaderos
static int embarcaderos(int origen, int destino,int longitudMatriz, int costo[][]) {

int resultado[][]=new int[longitudMatriz][longitudMatriz];
for(int i = 1; i < longitudMatriz; i++){
costo[i][i]=0;
}
for(int i = 1; i < longitudMatriz; i++){
for(int j = 1; j < longitudMatriz; j++){
menorDeLosCandidatos(i,j,longitudMatriz,costo,resultado);
}
}

return resultado[longitudMatriz][longitudMatriz];
}

//Funcion de menor de los candidatos
static int menorDeLosCandidatos(int origen,int destino,int longitud,int costo[][],int resultado[][]) {
int temporal;
//REVISAR CUAL ES EL VALOR MAXIMO
temporal = longitud;
for(int i = origen+1; i < longitud; i++){
temporal = minimo(temporal,(costo[origen][i])+(resultado[i][destino]));
}
return temporal;
}


static int minimo(int valorUno, int valorDos) {
int resultado;
if (valorUno<valorDos) {
resultado = valorUno;
}
else {
resultado = valorDos;
}
return resultado;
}

}
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

programación dinamica

Publicado por Nicolle (1 intervención) el 27/04/2020 18:21:04
Ya tienes el código funcionando que me lo puedas facilitar por favor?
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar