Algoritmos para el problema de los vales

(Esta entrada es continuación de ésta).

Recordatorio: el problema consiste en que queremos comprar unos productos de precios p_i y nos dan un vale de descuento por cada compra de C euros o mayor; así que tenemos que dividir los productos en varias compras, de forma que consigamos el mayor número posible de vales de descuento. En realidad, el planteamiento original era que el precio tenía que ser mayor que C.

Vale, ya sabemos que es imposible encontrar siempre rápidamente la mejor solución. ¿Pero cómo encontramos rápidamente una solución razonablemente buena?

Mi amigo sugirió este algoritmo:

Yo sugerí este otro. Tiene la pega de que hace falta suponer que todos los precios son múltiplos de un céntimo para poder calcular rápidamente la lista de todos los posibles precios.

• Mientras el precio de los artículos que quedan por pedir exceda C:
  • Averiguar el precio de pedido más pequeño que se puede hacer que exceda C
  • Encontrar un conjunto de artículos que tenga ese precio
  • Hacer un pedido con ese conjunto
• Añadir los artículos que sobran al último pedido, si se ha hecho algún pedido, o hacer con ellos el primer pedido.

Los dos algoritmos se ejecutan en tiempo polinómico, así que o bien P=NP y lo hemos resuelto, o bien estos algoritmos no siempre encuentran la solución óptima. He aquí dos ejemplos en los que fallan:

• C=20 y los precios son {6,6,6,7,8,9}. En este caso, el primer algoritmo falla, porque al meter los dos precios mayores en la misma compra se queda sin encontrar la solución óptima, que es {9,6,6}, {8,7,6}. El segundo algoritmo sí que acierta, porque es posible hacer una compra de 21, luego la otra también tiene que ser de 21.
• C=20 y los precios son {7,7,7,15,15,15}. Ahora el primer algoritmo acierta, porque encuentra la solución {7,15}, {7,15}, {7,15}, pero el segundo algoritmo falla, porque el precio más bajo superior a 20 es 21, así que empieza haciendo la compra {7,7,7}, y luego no puede conseguir dos vales más.