Desarrollo y diseño

[JAVA] Ejercicio similar mochila

willy_chaos
willy_chaos #1 Jun '14

Hola a todos, estoy haciendo un ejercicio estilo el de la mochila. Suponiendo que somos una empresa, por un lado tengo un fichero txt con clientes y el dinero que se ha gastado en nuestra empresa. Por otro lado tengo un fichero con productos y el precio que estos tienen.

Juntando eso, tengo que generar un fichero .txt que contenga

Nombre cliente --- lote de producto [ prod 1, prod 2, prod 3 ... ]

donde el lote tiene que tener el valor ( en productos ) de lo que el cliente se ha gastado en la empresa. No pueden haber lotes iguales.

--- La cosa es que estoy mirando el ejercicio de la mochila, pero claro ahi solo hay 1 cosa a rellenar con X productos. Aqui es como si cada lote fuera una mochila y sin repetirse...

Alguien puede darme unas pinceladas de como lo haria?

Ya tengo cargado en los array tanto los clientes como los productos, solo me falta lo dificil que es generar el array de lotes.

Mewtwo
Mewtwo #2 Jun '14

si me he enterado bien tienes una lista con clientes y lo que han gastado es decir :

cliente 1 = 1000 €
cliente 2 = 500€

y en el otro productos con su precio no ? y tienes que generar un lote que llegue aproximadamente al precio que ha gastado el cliente ?

willy_chaos
willy_chaos #3 Jun '14

Si, solo que ese lote no debe tener productos repetidos

Clientes.txt

El numero entre parentesis es el Coste del producto.

Productos

El resultado debe ser algo asi, solo salen dos ahora porque he creado lotes manualmente y se los he asignado, para ver si el metodo de escribir los lotes en fichero funciona.

[spoiler=][code]NOMBRE CLIENTE PRODUCTOS DEL LOTE

Guille Rodriguez Gonzalez Jamon, Pistachos, Producto4, Producto2, Esparragos

Andreu Jamon, Esparragos, Pistachos, Producto1, Producto2, Producto3, Producto4
---------------------------------------------------------------------------------------------------------------[/code][/spoiler]

Tengo todo realizado ( lo facil ) ahora me falta pues eso, como hacer esto mediante Backtracking o Branch & Bound

1 respuesta
Mewtwo
Mewtwo #4 Jun '14

#3
backtracking, puedes aplicar el algoritmo de la mochila para elementos no repetidos.

Coges el primer cliente miras cual es su tope y haces backtracking para calcular el lote de ese cliente , luego pasas al siguiente cliente e igual .

Te cuando cuidado a hacer backtracking que si esta mal implementado eso puede tardar cojon y medio, lo se por experiencia de dos personas haber realizado la misma practica , una tardaba 30 minutos con datos muy pequeños y la otra 3 segundos.

Usuarios habituales

  • Mewtwo
  • willy_chaos

Tags