Menos uso de estampillas para lograr un franqueo determinado

Question

Tiene hojas de 42 centavos sellos y 29 centavos sellos, pero necesita al menos $3,20 por correo un paquete. ¿Cuál es la cantidad mínima que usted puede hacer con el de 42 y 29 centavos sellos que es suficiente para enviar el paquete?

Un concurso de problema como este, es probablemente más fácil de resolver mediante la tabulación de las combinaciones posibles, el uso de 0 a través del techo(total/valor mayor) del mayor valor de las estampillas y calcular el número necesario de la más pequeña de las estampillas y el total de franqueo involucrados. El ejemplo anterior sería resuelto con un 9 fila de una tabla, que muestra el mínimo será de $3.23, hecha con 7 42 centavos sellos y 1 29-ciento sello.

Hay un mejor algoritmo para resolver este tipo de problema? ¿Qué pasa si usted tiene más de dos valores de sellos?

Answer 1

Con dos sellos, puedes hacerlo en forma lineal pseudo-lineal tiempo - O(costototal/costOfLargerStamp) - por la simple enumeración de todas las posibilidades (sólo hay un posible recuento de los más pequeños de la estampilla para cada uno de los cargos de los más grandes de cupones).

En general, sin embargo, la solución de esto es equivalente a resolver un general de programación lineal entera problema escrito en forma estándar, que es NP-completo.

Answer 2

Deje t ser su destino y a y b < a ser los valores de los sellos que se tienen. Deje n = ⌈t/a⌉ ser el número máximo de a sellos tiene sentido usar.

Para cada número i de n a 0, considerar el costo de la solución con:

• i sellos de valor a y
• j = ⌈(t - i*a) / b⌉ sellos de valor b

El costo de cada una de las soluciones sería, obviamente, i*a + j*b.

Su solución es el par (i, ⌈(t - i*a) / b⌉ ) que minimiza dicho coste. (Tenga en cuenta que sólo hay un desconocido en ese par, i.)

Una optimización adicional sería la de detener inmediatamente tan pronto como una división sin descanso se realiza, ya sea al determinar n o j. Una división sin descanso significa que hemos encontrado una solución que perfectamente se paga el importe debido y por lo tanto no puede ser mejor. (Puede haber otros como él, pero ninguno de ellos es realmente mejor, así que no hay necesidad de seguir buscando).

Answer 3

Es importante entender que la NP-completitud se define en términos de tamaño de entrada, no en términos de costo que debe ser pagado, C, o el número de tipos de sellos, S, cuando estamos tratando con números enteros en lugar de los números reales.

Este algoritmo, en realidad puede ser resuelto en tiempo de CS. Tomamos el primer valor de la marca de una marca de todos los múltiples de como obtenibles (hasta el menos número mayor que el costo). Entonces, para cada valor de la marca, nos marca como obtener todos los números que se pueden obtener mediante la adición de un múltiplo de su valor con una obtenible número (hasta el menos número mayor que el costo). Podemos seguir la pista de los más bajos el costo de franqueo cantidad que hemos encontrado hasta ahora.

Answer 4

Un problema similar se conoce en matemáticas. Es el llamado "Sello de correos" problema, y por lo general pide que se postal valores se pueden realizar y cuáles no. La programación dinámica es un común, pero no polinomio de tiempo de solución para esto. Un polinomio solución de tiempo de uso de fracciones continuas en el caso de los dos cupones de denominaciones existe, y los algoritmos más complejos que existen tres o más cupones de denominaciones. Buscar "Número de Frobenius" para obtener más información técnica.

Para el problema dado, me gustaría calcular aproximadamente el número de Frobenius, y se basa en la estimación de hacer una fácil adivinar como a un cerca de la solución y, a continuación, utilizar una programación dinámica/tabulares de solución, dependiendo de la cantidad de tiempo que tuve para resolver el problema.

Answer 5

Esta es una simple variación de la Mochila problema. Que es un NP-Completo el problema.

Deje que n sea el valor del objetivo, se puede resolver mediante la mochila de la dinámica de las soluciones de programación.

Si usted tiene una cantidad finita de sellos, entonces usted puede agregar todos ellos, reste el valor del objetivo. Ejecutar 0-1 mochila en los sellos con el número resultante. Los sellos de fuera de la mochila es la solución.

Si usted tiene una cantidad infinita de sellos. Usted puede hacerlos finito: $\lceil \frac{n}{t_i}\rceil$ sellos sellos con valor de $t_i$ y ejecutar el proceso anterior, o usted puede calcular el resultado de la ejecución de mochilas O(log n) veces similar a una búsqueda binaria.

No es mejor que un ingenuo retroceso solución cuando n es grande. Supongo que usted no va a pagar $100 para los sellos. ;)