El valor máximo de sellos de correos en un sobre

Question

El problema sello postal es un enigma matemático que le pregunta ¿cuál es el valor de franqueo más pequeño que no puede ser colocado en un sobre, si la carta puede contener sólo un número limitado de sellos, y de éstos sólo puede tener ciertos valores nominales especificados.

Por ejemplo, supongamos que el sobre puede contener sólo tres sellos, y los valores de indicación disponibles son de 1 centavo, 2 centavos, 5 centavos, y 20 centavos de dólar. Después, la solución es de 13 centavos; ya que cualquier valor más pequeño se puede obtener con un máximo de tres sellos (por ejemplo 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), pero para obtener 13 centavos uno debe utilizar al menos cuatro sellos.

¿Existe un algoritmo que da la máxima cantidad de sellos permitidos y el valor nominal de los sellos, uno puede encontrar el franqueo más pequeño que no puede ser colocado en el sobre?

Otro ejemplo:
Máximo de 5 sellos se puede utilizar
Valorado: 1, 4, 12, 21
El valor más pequeño que no se puede alcanzar es 72. Valores 1-71 se pueden crear con una cierta combinación.

Al final, probablemente va a utilizar Java para este código.

Answer 1

Sí, existe tal algoritmo un. Ingenuamente: empezando por 1, probar todas las combinaciones posibles de sellos hasta que encontremos una combinación que produce una suma de 1, entonces tratamos de 2, y así sucesivamente. Sus algoritmo termina cuando se encuentra un número tal que ninguna combinación de sellos añade a ese número.

Aunque posiblemente lenta, para los pequeños problemas suficientes (por ejemplo 100 sellos, 10 posiciones) se puede resolver esto de una cantidad "razonable" de tiempo ...

Sin embargo, para grandes problemas, aquellos en los que tenemos muchos sellos disponibles (digamos 1000) y muchas posiciones posibles (digamos 1000), este algoritmo puede tomar una cantidad de tiempo intratable. Es decir, en caso de grandes problemas, el tiempo para resolver el problema con este enfoque podría ser por ejemplo, el tiempo de vida del universo, y por lo tanto no es realmente útil para usted.

Si usted tiene realmente grandes problemas que necesita para encontrar maneras de acelerar su búsqueda, estas aceleraciones se llama heurística. No se puede superar el problema, pero que posiblemente puede resolver el problema más rápido que el enfoque ingenuo mediante la aplicación de algún tipo de conocimiento del dominio.

Una forma sencilla de mejorar este enfoque ingenuo podría ser que cada vez que intente una combinación de sellos que no es igual al número que está buscando se quita esa combinación del conjunto posible probar por cualquier número futuro, y marcar ese número futuro como no disponible. Dicho de otra manera:. Mantenga una lista de números que has encontrado ya y las combinaciones que le consiguió allí, entonces no pongan cara de esos números o sus combinaciones nuevo

Answer 2

Aquí es otra punta:. Cada conjunto de sellos que se suma a un número dado se puede formar mediante la adición de 1 sello para un conjunto de tamaño mínimo de sellos que se suma a menos de ese número

Por ejemplo, supongamos que tenemos los sellos 1, 2, 7, 12 y 50, y un límite de 5 sellos, y queremos saber si 82 ??se puede representar. Para conseguir que el 82, debe agregar:

• A 1 a un conjunto de sellos adición de hasta 82-1 = 81, o
• A 2 a un conjunto de sellos adición de hasta 82-2 = 80, o
• A 7 a un conjunto de sellos adición de hasta 82-7 = 75, o
• A 12 a un conjunto de sellos adición de hasta 82-12 = 70, o
• A 50 a un conjunto de sellos que suman 82-50 = 32.

Esas son las únicas maneras posibles que se pueden formar 82. Entre todos esos 5 posibilidades, una (o posiblemente más de uno) tendrá el número mínimo de sellos. Si ese número mínimo es> 5, a continuación, 82 no pueden representarse con sellos.

Nótese también que si un número se puede representar, es necesario registrar el número mínimo de sellos necesarios para ello por lo que los cálculos de los números más altos pueden utilizarlo.

Esto, más de Steve Jessop respuesta , se espera obtener su mente en el camino correcto para una solución de programación dinámica ... Si todavía tienes ni idea, que me haga saber.

Answer 3

En lugar de computar de manera exhaustiva las sumas de todas las posibles combinaciones de sellos (quizá por la recursividad), tenga en cuenta todas las posibles sumas , y el trabajo de lo que el menor número de sellos es producir cada suma. Hay un montón de combinaciones de sellos, pero mucho menos sumas distintas.

En el ejemplo que dio en un comentario, 10 sellos caber en un sobre, y ningún sello tiene un valor superior a 100. Hay combinaciones n^10 de sellos, donde n es el número de denominaciones de sello disponible. Pero la mayor suma posible de 10 sellos sólo es 1000. Crear un array hasta 1001, y tratar de pensar en una forma eficiente de hacer ejercicio, para todos aquellos valores juntos, el menor número de sellos requiere para hacer cada uno. Su respuesta es entonces lo menos índice de requerir 11 (o más) sellos, y se puede coronar cada sello de conteo en 11, también.

"eficiente" en este caso significa, básicamente, "evitar la repetición de cualquier trabajo que no tienen que". Así que vas a querer volver a utilizar los resultados intermedios tanto como sea posible.

Si eso no es suficiente de una pista a continuación, o bien (a) me equivoco en el enfoque (en cuyo caso, lo siento, no he resuelto el problema en realidad a mí mismo antes de contestar) o (b) la actualización de decir qué tan lejos han conseguido a lo largo de esas líneas.

Answer 4

Tal vez sea un poco inútil dar sólo "sugerencias" sobre una solución de DP cuando se especula que uno ni siquiera existe. Así que aquí es ejecutable código Perl implementar el algoritmo de DP real:

#!/usr/bin/perl
my ($n, @stamps) = @ARGV;
my @_solved;        # Will grow as necessary

# How many stamps are needed to represent a value of $v cents?
sub solve($) {
    my ($v) = @_;
    my $min = $n + 1;

    return 0 if $v == 0;

    foreach (@stamps) {
        if ($v >= $_) {
            my $try = $_solved[$v - $_] + 1;
            $min = $try if $try < $min;
        }
    }

    $_solved[$v] = $min;
    return $min;
}

my $max = (sort { $a <=> $b } @stamps)[-1];

# Main loop
for (my $i = 0; $i <= $max * $n; ++$i) {
    my $ans = solve($i);
    if ($ans > $n) {
        print "$i cannot be represented with <= $n stamps of values " . join(", ", @stamps) . ".\n";
        last;
    }
}

Normalmente solve() requeriría una llamada recursiva, sino porque siempre tratamos los valores en el orden 0, 1, 2, 3 ..., sólo podemos utilizar la matriz @_solved directamente para obtener la respuesta para los tamaños más pequeños de problemas.

Esto se lleva a 93ms en mi PC para resolver el caso de los tamaños sello 1, 4, 12, 21 y sobre de tamaño 1000. (La respuesta es 20967.) Un lenguaje compilado será aún más rápido.

Answer 5

        import java.util.ArrayList;
        import java.util.List;
        /**
         * 
         * @author Anandh
         *
         */
        public class MinimumStamp {

            /**
             * @param args
             */
            public static void main(String[] args) {
                // TODO Auto-generated method stub
                int stamps[]={90,30,24,15,12,10,5,3,2,1};
                int stampAmount = 70;
                List<Integer> stampList = minimumStamp(stamps, stampAmount);
                System.out.println("Minimum no.of stamps required-->"+stampList.size());    
                System.out.println("Stamp List-->"+minimumStamp(stamps, stampAmount));  
            }

            public static List<Integer> minimumStamp(int[] stamps, int totalStampAmount){
                List<Integer> stampList =  new ArrayList<Integer>();
                int sumOfStamps = 0;
                int remainingStampAmount = 0;
                for (int currentStampAmount : stamps) {
                    remainingStampAmount = totalStampAmount-sumOfStamps;
                    if(remainingStampAmount%currentStampAmount == 0){
                        int howMany = remainingStampAmount / currentStampAmount;
                        while(howMany>0){
                            stampList.add(currentStampAmount);
                            howMany--;
                        }
                        break;
                    }else if(totalStampAmount == (sumOfStamps+currentStampAmount)){
                        stampList.add(currentStampAmount);
                        break;
                    }else if(totalStampAmount > (sumOfStamps+currentStampAmount) ){
                        int howMany = remainingStampAmount / currentStampAmount;
                        if(howMany>0){
                            while(howMany>0){
                                stampList.add(currentStampAmount);
                                sumOfStamps += currentStampAmount;
                                howMany--;
                            }
                        }else{
                            stampList.add(currentStampAmount);
                            sumOfStamps += currentStampAmount;
                        }
                    }
                }
                return stampList;
            }
        }