Problema de backtracking
Publicado por Estudiante1234 (1 intervención) el 07/05/2022 12:42:24
Buenos días,
Tengo este problema para resolverlo con backtracking pero no tengo muy claro como hacerlo con Java, como no se le asigna ningún valor a los paquetes no se muy bien como resolverlo.
Una empresa de mudanzas deberá transportar todos los paquetes, bien con un solo camión en varios viajes, o bien con varios camiones y un viaje cada uno. Suponemos lo segundo (aunque el problema es equivalente), y se pretende usar la menor cantidad posible de camiones.
Se pide: un algoritmo backtracking que distribuye todos los paquetes en la menor cantidad posible de camiones. La solución, si existe, debe ser siempre óptima, sin limite de orden de complejidad. Suponemos que hay un máximo de camiones y todos con la misma capacidad.
Entrada/Salida:
Entrada: Peso de los paquetes, cantidad de camiones y su capacidad.
Salida: Cantidad mínima de camiones y asignación a cada paquete de su camión. Suponemos los camiones numerados desde 1. Si no hay suficientes camiones o algún paquete supera la capacidad máxima no hay solución.
Tengo este problema para resolverlo con backtracking pero no tengo muy claro como hacerlo con Java, como no se le asigna ningún valor a los paquetes no se muy bien como resolverlo.
Una empresa de mudanzas deberá transportar todos los paquetes, bien con un solo camión en varios viajes, o bien con varios camiones y un viaje cada uno. Suponemos lo segundo (aunque el problema es equivalente), y se pretende usar la menor cantidad posible de camiones.
Se pide: un algoritmo backtracking que distribuye todos los paquetes en la menor cantidad posible de camiones. La solución, si existe, debe ser siempre óptima, sin limite de orden de complejidad. Suponemos que hay un máximo de camiones y todos con la misma capacidad.
Entrada/Salida:
Entrada: Peso de los paquetes, cantidad de camiones y su capacidad.
Salida: Cantidad mínima de camiones y asignación a cada paquete de su camión. Suponemos los camiones numerados desde 1. Si no hay suficientes camiones o algún paquete supera la capacidad máxima no hay solución.
Valora esta pregunta
-1