Valore massimo dei francobolli su una busta

Question

Il problema del francobollo è un indovinello matematico che chiede qual è il valore di affrancatura più piccolo che non può essere inserito su una busta, se la lettera può contenere solo un numero limitato di francobolli, e questi possono hanno solo determinati valori facciali specificati.

Ad esempio, si supponga che la busta possa contenere solo tre timbri ei valori di timbri disponibili sono 1 cent, 2 centesimi, 5 centesimi e 20 centesimi. Quindi la soluzione è di 13 centesimi; poiché qualsiasi valore più piccolo può essere ottenuto con al massimo tre timbri (ad esempio 4 = 2 + 2, 8 = 5 + 2 + 1, ecc.), ma per ottenere 13 centesimi è necessario utilizzare almeno quattro timbri.

Esiste un algoritmo che fornisce la quantità massima di francobolli consentiti e il valore nominale dei francobolli, si può trovare la più piccola spedizione che non può essere posizionata sulla busta?

altro esempio:
massimo di 5 francobolli possono essere usati
stimato: 1, 4, 12, 21
Il valore minimo che non può essere raggiunto è 72. I valori 1-71 possono essere creati con una certa combinazione .

Alla fine probabilmente userò Java per codificarlo.

Answer 1

Sì, c'è un tale algoritmo. Ingenuamente: iniziando con 1, prova ogni possibile combinazione di francobolli finché non troviamo una combinazione che produce una somma di 1, quindi prova per 2 e così via. Il tuo algoritmo termina quando trova un numero tale che nessuna combinazione di francobolli aggiunge a quel numero.

Anche se forse lenta, se hai problemi abbastanza piccolo (diciamo 100 francobolli, 10 posizioni) si può risolvere questo in una quantità "ragionevole" di tempo ...

Ma, per i grandi problemi, quelli in cui abbiamo molti francobolli disponibili (ad esempio 1000 s) e molte posizioni possibili (ad esempio 1000 s), questo algoritmo potrebbe richiedere una quantità di tempo irrisolvibile. Cioè, per problemi molto grandi, il tempo di risolvere il problema usando questo approccio potrebbe essere, la vita dell'universo, e quindi non è davvero utile per te.

Se hai problemi davvero grossi hai bisogno di trovare modi per velocizzare la tua ricerca, questi speedup sono chiamati euristici. Non è possibile superare il problema, ma è possibile risolvere il problema più velocemente dell'approccio ingenuo applicando una sorta di conoscenza del dominio.

Un modo semplice per migliorare questo approccio ingenuo potrebbe essere che ogni volta che provi una combinazione di francobolli che non corrisponde al numero che stai cercando, rimuovi questa combinazione dal set possibile per provare per qualsiasi numero futuro, e segna quel numero futuro come non disponibile. Detto in un altro modo: mantieni una lista di numeri che hai già trovato e le combinazioni che ti hanno portato lì, quindi non cercare di nuovo quei numeri o le loro combinazioni.

Answer 2

Piuttosto che calcolare in modo esaustivo le somme di tutte le possibili combinazioni di francobolli (forse con ricorsione), considerare tutte le possibili e calcolare il numero minimo di francobolli per produrre ciascuna somma. Ci sono un sacco di combinazioni di francobolli, ma molto meno somme distinte.

Nell'esempio hai dato in un commento, 10 francobolli stare su una busta, e nessun timbro ha un valore maggiore di 100. Ci sono n^10 combinazioni di timbri, dove n è il numero di denominazioni di timbro a disposizione. Ma la somma massima di 10 francobolli è solo 1000. Crea un array fino a 1001 e prova a pensare a un modo efficace per calcolare insieme, per tutti quei valori, il numero minimo di timbri necessari per realizzarli.La tua risposta è quindi il minimo indice che richiede 11 (o più) timbri, e puoi anche limitare ogni numero di francobollo a 11.

"Efficiente" in questo caso significa sostanzialmente "evitare di ripetere qualsiasi lavoro non necessario". Quindi vorrai riutilizzare il più possibile i risultati intermedi.

Se questo non è abbastanza di un suggerimento allora o (a) ho sbagliato l'approccio (nel qual caso mi dispiace, non ho in realtà risolto il problema io stesso prima di rispondere) o (b) aggiornamento per dire fino a che punto hai capito queste linee.

Answer 3

Ecco un altro suggerimento: Ogni set di timbri che si aggiunge a un determinato numero può essere formato aggiungendo 1 timbro a un set di timbri di dimensioni minime che aggiunge un numero inferiore a quel numero.

Ad esempio, supponiamo di avere i timbri 1, 2, 7, 12 e 50 e un limite di 5 timbri, e vogliamo scoprire se 82 può essere rappresentato. Per ottenere che l'82, è necessario aggiungere:

• A 1 ad una serie di francobolli che aggiungono fino a 82-1 = 81, o
• A 2 ad una serie di francobolli che aggiungono fino a 82-2 = 80, o
• a 7 ad una serie di Stamp aggiungendo fino a 82-7 = 75, o
• a 12 ad una serie di Stamp aggiungendo fino a 82-12 = 70, o
• a 50 ad una set di timbri con un massimo di 82-50 = 32.

Questi sono gli unici modi possibili in cui è possibile creare 82. Tra tutte queste 5 possibilità, una (o forse più di una) avrà il numero minimo di francobolli. Se quel numero minimo è> 5, allora 82 non può essere rappresentato con timbri.

Si noti inoltre che se un numero può essere rappresentato, è necessario registrare il numero minimo di timbri necessari per esso in modo che i calcoli per numeri più alti possano utilizzarlo.

Questo, più Steve Jessop's answer, si spera che tu possa avere la mente sulla strada giusta per una soluzione di programmazione dinamica ... Se sei ancora perplesso, fammi sapere.

Answer 4

Forse è un po 'inutile dare solo "suggerimenti" su una soluzione DP quando esiste la speculazione che ne esiste uno. Così qui è eseguibile codice Perl implementazione dell'algoritmo DP attuale:

#!/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() richiederebbe una chiamata ricorsiva, ma perché cerchiamo sempre valori nell'ordine 0, 1, 2, 3 ..., possiamo solo utilizzare direttamente l'array @_solved per ottenere la risposta in caso di problemi di dimensioni minori.

Questo richiede 93 ms sul mio PC per risolvere il caso per le dimensioni di timbri 1, 4, 12, 21 e dimensione busta 1000. (La risposta è 20967.) Un linguaggio compilato sarà ancora più veloce.

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; 
      } 
     }