PHP - Reparto componentes vector en matriz

Buenas tardes! Recurro mucho a esta web cuando tengo dudas, pero nunca me había animado a escribir una consulta. No encuentro nada parecido, y seguramente será porque no estoy buscando correctamente, pero voy con mi duda a ver si me podéis ayudar:

Estoy intentando crear un algoritmo de reparto de pedidos dentro de un camión de reparto. Vamos con un ejemplo, que se verá mejor:

Imaginemos que tenemos que repartir 3 pedidos:
Pedido 1 - 11000 litros de gasoleo A
Pedido 2 - 14000 litros de gasoleo B
Pedido 3 - 7000 litros de gasoleo C

Y nuestro vehículo tiene los siguientes compartimientos:
Depósito 1 - 10000 litros de capacidad
Depósito 2 - 5000 litros de capacidad
Depósito 3 - 5000 litros de capacidad
Depósito 4 - 7000 litros de capacidad
Depósito 5 - 5000 litros de capacidad
Depósito 6 - 5000 litros de capacidad

No se pueden mezclar los pedidos, si un pedido tiene que ocupar 2 o más compartimentos, esos se han quedado ya bloqueados para ese pedido, aunque sobre espacio.

- Si tenemos más pedidos que depósitos, devolveremos error.

- Si la suma de pedidos es mayor que la capacidad de los depósitos, devolveremos error.

Ahora vienen los problemas. Haciendo pruebas en papel, con distintas posibilidades de pedidos iniciales, hay varias soluciones para un mismo problema, aunque si se pudiera elegir, la solución óptima pasaría por rellenar el camión desde el depósito 1 hacia el 6. Hay veces que si te pones a rellenar linealmente el pedido 1 en el depósito 1 (o 1 y 2, si no cabe, etc), al final te falta camión, y si hubieras empezado por otro pedido sí que te cuadraría todo dentro del camión. Creo que sería interesante ordenar los pedidos por tamaño, de mayor a menor, y después empezar a probar las combinaciones.



Alguna idea?


Gracias!
Un saludo

Hola,

pero los pedidos siempre tienen ese valor? Quiero decir: si el usuario tiene la opción de seleccionar los litros, puedes crear un selector para que el user solo pueda seleccionar una opción..

Pero estaría bien que añadieras algo más de info porque así es un poco complicado..

Gracias ;)

Hola! Los valores que he puesto son un ejemplo, el usuario puede introducir tantos pedidos como depósitos distintos tiene el camión, y de la cantidad que quiera. Es decir, es tan válida una entrada de 1 sólo pedido de 32000 litros, como una entrada de 4 pedidos con cantidades (7000, 12000, 10000, 4000) por ejemplo.

Una manera de hacerlo es ir pedido a pedido probando en los compartimentos. En la primera ronda se encaja el pedido que quepa en cada depósito individualmente. Si quedan pedidos sin colocar, se inicia una nueva ronda probando a combinar 2 depósitos para que quepa el pedido, y así sucesivamente. Pero esta solución me parece que se dejaría muchas combinaciones fuera de la prueba, porque cogería el vector de pedidos desde el principio al último elemento, y trataría de encajar cada uno dentro del camión en rondas de 1 depósito, 2 depósitos, etc. Pero nunca probaríamos a encontrar una solución mejor si empezamos con otro orden de pedidos, etc.

Está mejor aclarado ahora? :)


Gracias,
Un saludo