Valor máximo de estampillas en un sobre

Question

El problema del sello postal es un acertijo matemático que pregunta cuál es el valor de franqueo más pequeño que no se puede colocar en un sobre, si la letra solo puede contener un número limitado de sellos, y estos pueden solo tiene ciertos valores nominales especificados.

Por ejemplo, supongamos que el sobre solo puede contener tres sellos, y los valores de sello disponibles son 1 centavo, 2 centavos, 5 centavos y 20 centavos. Entonces la solución es 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 se deben usar al menos cuatro sellos.

¿Hay un algoritmo que, dada la cantidad máxima de sellos permitidos y el valor nominal de los sellos, uno puede encontrar el franqueo más pequeño que no se puede colocar en el sobre?

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

Al final probablemente usaré Java para codificar esto.

Answer 1

Sí, existe tal algoritmo. Ingenuamente: comenzando con 1, pruebe todas las combinaciones posibles de sellos hasta que encuentre una combinación que arroje una suma de 1, luego intente con 2, y así sucesivamente. Su algoritmo termina cuando encuentra un número tal que ninguna combinación de sellos se agrega a ese número.

aunque posiblemente lenta, por problemas lo suficientemente pequeñas (digamos 100 sellos, 10 posiciones) se puede resolver esto de una cantidad "razonable" de tiempo ...

Pero, para los grandes problemas, aquellos en los que tenemos muchos sellos disponibles (digamos 1000s) y muchas posiciones posibles (digamos 1000s), este algoritmo podría tomar una cantidad de tiempo intratable. Es decir, para problemas muy grandes, el tiempo para resolver el problema usando este enfoque podría ser, por ejemplo, la duración del universo, y por lo tanto no es realmente útil para usted.

Si tiene problemas realmente grandes, necesita encontrar formas de acelerar su búsqueda, estas aceleraciones se llaman heurística. No puedes vencer el problema, pero posiblemente puedas resolver el problema más rápido que el enfoque ingenuo aplicando algún tipo de conocimiento de dominio.

Una manera simple de mejorar este enfoque ingenuo podría ser que cada vez que pruebe una combinación de sellos que no sea igual al número que está buscando, elimine esa combinación del posible conjunto para intentar cualquier número futuro, y marque ese número futuro como no disponible. Dicho de otra manera: conserve una lista de los números que ya encontró y las combinaciones que lo llevaron allí, luego no busque esos números o sus combinaciones nuevamente.

Answer 2

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 trabajar en lo que el menor número de sellos es producir cada suma. Hay muchas combinaciones de sellos, pero muchas menos sumas distintas.

En el ejemplo, usted dio un comentario, 10 sellos caben en un sobre y ningún sello tiene un valor mayor que 100. Hay n^10 combinaciones de sellos, donde n es el número de denominaciones de sello disponibles. Pero la suma más grande posible de 10 sellos es solo 1000. Cree una matriz de hasta 1001 y trate de pensar en una forma eficiente de trabajar, para todos esos valores en conjunto, la menor cantidad de sellos necesarios para hacer cada uno.Su respuesta es, entonces, el índice más bajo que requiere 11 (o más) sellos, y también puede limitar cada cuenta de sellos a 11.

"Eficiente" en este caso básicamente significa, "evite repetir cualquier trabajo que no tenga que hacer". Por lo tanto, querrá volver a utilizar los resultados intermedios tanto como sea posible.

Si eso no es suficiente una pista, entonces (a) estoy equivocado sobre el enfoque (en cuyo caso lo siento, no he resuelto el problema antes de responder) o (b) actualizar para decir qué tan lejos te llevas bien con esas líneas

Answer 3

Aquí hay otro consejo: Cada conjunto de sellos que se suman a un número dado se puede formar agregando 1 sello a un conjunto de sellos de tamaño mínimo que suma 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 se puede representar 82. Para conseguir que el 82, debe agregar:

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

Esas son las únicas formas posibles de formar 82. Entre todas esas 5 posibilidades, una (o posiblemente más de una) tendrá la cantidad mínima de sellos. Si ese número mínimo es> 5, entonces 82 no se puede representar con sellos.

Observe también que si se puede representar un número, debe registrar el número mínimo de sellos necesarios para que los cálculos con números más altos puedan usarlo.

Esto, más Steve Jessop's answer, con suerte lo guiará en la dirección correcta para una solución de programación dinámica ... Si todavía está perplejo, hágamelo saber.

Answer 4

Tal vez es un poco inútil dar "pistas" sobre una solución de DP cuando hay especulaciones de que existe una. Así que aquí es ejecutable código Perl implementar el algoritmo real DP:

#!/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; 
    } 
} 

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

Esto lleva 93ms en mi PC para resolver el caso de los tamaños de sellos 1, 4, 12, 21 y el sobre 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; 
      } 
     }