valore massimo di francobolli su una busta

Question

Il problema francobollo è un rompicapo matematico che chiede qual è il valore di affrancatura più piccolo che non può essere posizionato su una busta, se la lettera può contenere solo un numero limitato di Stamp, e questi possono avere solo certi valori nominali specificati.

Ad esempio, si supponga che la busta può contenere solo tre Stamp, ei valori provvisorie sono disponibili 1 centesimo, 2 centesimi, 5 centesimi e 20 centesimi. Quindi la soluzione è 13 centesimi; poiché qualsiasi valore inferiore può essere ottenuta con più di tre francobolli (esempio 4 = 2 + 2, 8 = 5 + 2 + 1, ecc), ma per ottenere 13 centesimi si deve utilizzare almeno quattro francobolli.

C'è un algoritmo che, data la quantità massima di francobolli consentiti e il valore nominale dei francobolli, si può trovare il più piccolo spese di spedizione che non può essere collocato sulla busta?

Un altro esempio:
Un massimo di 5 francobolli può essere utilizzato
Valued: 1, 4, 12, 21
Il valore più piccolo che non può essere raggiunta è 72. I valori 1-71 possono essere creati con una certa combinazione.

Alla fine io probabilmente utilizzerò Java per codice di questo.

Answer 1

Sì, c'è un algoritmo. Ingenuamente: a partire da 1, provare ogni possibile combinazione di francobolli fino a trovare una combinazione che produce una somma di 1, quindi provare per 2, e così via. Vostro algoritmo finiture quando trova un numero tale che nessuna combinazione di francobolli aggiunge a quel numero.

Anche se forse lento, per i piccoli problemi abbastanza (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 (dire 1000s) e molte posizioni possibili (diciamo 1000), questo algoritmo potrebbe richiedere una quantità di tempo intrattabile. Cioè, per problemi molto grandi, il tempo necessario per risolvere il problema utilizzando questo approccio potrebbe essere ad esempio, la durata di vita dell'universo, e quindi non è davvero utile a voi.

Se si hanno veramente grandi problemi è necessario trovare il modo per accelerare la ricerca, questi incrementi nella velocità sono chiamati euristica. Non si può battere il problema, ma si può eventualmente risolvere il problema più velocemente di quanto l'approccio ingenuo applicando una sorta di conoscenza di dominio.

Un modo semplice per migliorare questo approccio ingenuo potrebbe essere che ogni volta che si tenta una combinazione di francobolli che non è uguale al numero che stai cercando di rimuovere quella combinazione dal possibile set di provare per un numero qualsiasi futuro e marcare quel numero futuro come non disponibile. Detto in altro modo:. Tenere un elenco di numeri che hai trovato già e le combinazioni che ha ottenuto lì, quindi non si guarda per quei numeri o loro combinazioni di nuovo

Answer 2

Ecco un'altra punta:. Ogni set di Stamp che aggiunge fino a un dato numero può essere formato aggiungendo 1 timbro a un insieme minimo di dimensioni di Stamp che aggiunge fino a meno di quel numero

Per esempio, supponiamo di avere i timbri 1, 2, 7, 12, e 50, e un limite di 5 francobolli, e vogliamo sapere se 82 possono essere rappresentati. Per ottenere che l'82, è necessario aggiungere:

• A 1 ad una serie di Stamp aggiungendo fino a 82-1 = 81, o
• A 2 ad una serie di Stamp aggiungendo 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 serie di Stamp aggiungendo fino a 82-50 = 32.

Queste sono possibili solo modi che 82 possono essere formati. Tra tutti quei 5 possibilità, una (o forse più di uno) avrà il numero minimo di Stamp. Se tale numero minimo è> 5, quindi 82 non può essere rappresentato con francobolli.

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

Questo, più di Steve Jessop risposta , si spera ottenere la vostra mente sulla strada giusta per una soluzione di programmazione dinamica ... Se siete ancora perplessi, me lo faccia sapere.

Answer 3

Invece di esaustivamente calcolare le somme di tutte le possibili combinazioni di francobolli (forse di ricorsione), in considerazione tutti i possibili somme , e il lavoro che cosa il minor numero di francobolli è quello di produrre ogni somma. Ci sono un sacco di combinazioni di francobolli, ma molto meno somme distinte.

Nel esempio che ha dato in un commento, 10 francobolli stare su una busta, e nessun timbro ha un valore maggiore di 100. Ci sono combinazioni n^10 di francobolli, dove n è il numero di denominazioni di timbro a disposizione. Ma la più grande quantità possibile di 10 francobolli è solo 1000. Creare una matrice fino al 1001, e provare a pensare a un modo efficace per lavorare fuori, per tutti quei valori insieme, il minor numero di francobolli tenuto a fare ciascuno di essi. La tua risposta è quindi l'indice minimo che richiede 11 (o più) francobolli, e si può ricoprire ogni francobollo-count alle 11, anche.

"efficiente" in questo caso significa fondamentalmente, "evitare di ripetere qualsiasi lavoro che non c'è bisogno di". Così si sta andando a voler riutilizzare i risultati intermedi, per quanto possibile.

Se questo non è abbastanza di un indizio, allora (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 quanto lontano 've ha ottenuto in questo senso.

Answer 4

Forse è un po 'inutile per solo dare "suggerimenti" di una soluzione DP quando v'è la speculazione che ne esiste uno anche. 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;
    }
}

Di solito solve() richiederebbe una chiamata ricorsiva, ma perché cerchiamo sempre valori nell'ordine 0, 1, 2, 3 ..., possiamo semplicemente utilizzare la matrice @_solved direttamente per ottenere la risposta per le dimensioni più piccole problematiche.

Questo richiede 93ms sul mio PC per risolvere il caso per il timbro di dimensioni 1, 4, 12, 21 e busta di formato 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;
            }
        }