Maximalwert der Briefmarke auf einem Umschlag

Question

Die Briefmarke Problem ist ein mathematisches Rätsel, das fragt, was den kleinsten Portowert ist, die nicht auf einem Umschlag gelegt werden kann, wenn der Brief nur eine begrenzte Anzahl von Briefmarken halten kann, und diese nur bestimmte vorgegebene Nennwerte hat.

Beispiel: Angenommen, der Umschlag nur drei Stempel halten kann, und die zur Verfügung stehenden Stempelwert 1 Cent, 2 Cent, 5 Cent und 20 Cent. Dann wird die Lösung 13 Cent; da jeder kleinerer Wert kann mit höchstens drei Marken (z 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), aber zu bekommen 13 Cent erhalten werden, um einen mindestens vier Stempel verwenden muß.

Gibt es einen Algorithmus, der die maximale Menge an Briefmarken gegeben erlaubt und den Nennwert der Briefmarken kann man das kleinste Porto finden, das nicht auf dem Umschlag platziert werden?

Ein weiteres Beispiel:
Maximal 5 Marken können
verwendet werden Bewunderte: 1, 4, 12, 21
Der kleinste Wert, der nicht erreicht werden kann, ist 72 Werte 1-71 können mit einer bestimmten Kombination erstellt werden.

Am Ende werde ich wohl dieses Java-Code verwenden.

Answer 1

Ja, es ist ein solcher Algorithmus. Naiv: beginnend mit 1, versucht, jede mögliche Kombination von Briefmarken, bis wir eine Kombination finden, das eine Summe von 1 ergibt, dann versuchen, für 2, und so weiter. Ihr Algorithmus endet, wenn es eine solche Zahl ist, stellt fest, dass keine Kombination von Briefmarken zu dieser Zahl hinzu.

Wenn auch möglicherweise langsam, für klein genug, um Probleme (100 Briefmarken sagen, 10 Positionen) Sie dies in einer „vernünftigen“ Höhe der Zeit lösen können ...

Aber für große Probleme, diejenigen, bei denen wir viele Briefmarken verfügbar haben (sagen 1000s) und viele möglichen Positionen (sagen 1000s), dieser Algorithmus könnte eine unlösbare Menge Zeit in Anspruch nehmen. Das heißt, für sehr große Probleme, die Zeit, das Problem mit diesem Ansatz zu lösen könnte sagen, sein, um die Lebensdauer des Universums, und somit ist es nicht wirklich nützlich für Sie.

Wenn Sie wirklich große Probleme, die Sie müssen Wege finden, um die Suche zu beschleunigen, werden diese speedups Heuristik bezeichnet. Sie können das Problem nicht schlagen, aber Sie können möglicherweise das Problem schneller als der naive Ansatz lösen, indem sie eine Art von Domain-Wissen anwenden.

Ein einfacher Weg, diesen naiven Ansatz verbessern könnte sein, dass jedes Mal, wenn eine Kombination von Briefmarken versuchen, die nicht die Nummer nicht gleich Sie suchen Sie, dass die Kombination aus dem möglichen Satz entfernen für zukünftige Nummer zu versuchen, und markiert, dass die künftige Zahl als nicht verfügbar. Anders ausgedrückt:. Eine Liste von Zahlen halten Sie bereits und die Kombinationen gefunden haben, die Sie dort ankamen, dann suchen Sie nicht noch einmal für die Zahlen oder deren Kombinationen

Answer 2

Hier ist ein weiterer Tipp:. Jeder Satz von Briefmarken, die durch Zugabe von 1 Stempel auf ein Minimum großen Satz von Briefmarken gebildet wird, kann zu einer gegebenen Zahl addiert werden, als diese Zahl auf weniger aufaddiert

Angenommen, wir haben die Stempel 1, 2, 7, 12 und 50 und eine Grenze von 5 Briefmarken, und wir wollen herausfinden, ob 82 dargestellt werden kann. Um sicherzustellen, dass 82 zu erhalten, müssen Sie hinzufügen, entweder:

• A 1 auf einen Satz von Stempeln zu 82-1 = 81 Aufaddieren oder
• A 2 mit einem Satz von Stempeln zu 82-2 = 80 Aufaddieren oder
• A 7 auf einen Satz von Stempeln zu 82-7 = 75 Aufaddieren oder
• A 12 auf einen Satz von Stempeln zu 82-12 = 70 Aufaddieren oder
• A 50 auf einen Satz von Stempeln zu 82-50 = 32 Aufaddieren.

Das sind die einzigen Möglichkeiten, dass 82 gebildet werden kann. Unter allen diesen fünf Möglichkeiten, eine (oder möglicherweise mehr als eine) wird die Mindestanzahl von Briefmarken haben. Wenn die Mindestanzahl> 5, dann 82 kann nicht mit Briefmarken dargestellt werden.

Beachten Sie auch, dass, wenn eine Zahl dargestellt werden kann, müssen Sie die Mindestanzahl von Briefmarken für sie notwendig, um aufzuzeichnen, so dass die Berechnungen für höhere Zahlen können es verwenden.

Dies und Steve Jessop Antwort , hoffentlich bekommen Geist auf dem richtigen Weg für eine dynamische Programmierung Lösung ... Wenn Sie noch nicht gefunden haben, lassen Sie es mich wissen.

Answer 3

Anstatt abschließend die Summen aller möglichen Kombinationen von Briefmarken Berechnung (vielleicht durch Rekursion), sollten alle möglichen Summen , und herausfinden, was die kleinste Anzahl von Briefmarken ist jede Summe zu erzeugen. Es gibt viele Kombinationen von Briefmarken, aber viel weniger deutliche Summen.

Im Beispiel Sie in einem Kommentar gaben, 10 Marken auf einem Umschlag passen, und kein Stempel hat einen Wert von mehr als 100. Es gibt n^10 Kombinationen von Briefmarken, wo n ist die Anzahl der Stückelung des Stempels zur Verfügung. Aber die größtmögliche Summe von 10 Marken ist nur 1000 ein Array 1001 Erstellen Sie auf und versucht, eine effiziente Art und Weise zu denken, zu erarbeiten, für all diese Werte zusammen, die geringste Anzahl von Briefmarken erforderlich, um jeden zu machen. Ihre Antwort ist dann der kleinste Index erfordert 11 (oder mehr) Briefmarken, und Sie können jede Stempelzahl bei 11, begrenzen.

„Efficient“ in diesem Fall grundsätzlich Mittel „nicht wiederholt jede Arbeit, die Sie nicht haben“. So wird dich wie möglich wiederverwendet Zwischenergebnisse so viel wollen.

Wenn das nicht genug von einem Hauch dann entweder (a) Ich bin falsch über die Vorgehensweise (in diesem Fall leid, ich habe nicht wirklich löste das Problem selbst, bevor er antwortet) oder (b) Update zu sagen, wie weit Sie ‚ve in diese Richtung habe.

Answer 4

Vielleicht ist es ein bisschen wenig hilfreich, nur „Hinweise“ über eine DP-Lösung zu geben, wenn es Spekulation ist, dass man existiert. So, hier ist runnable Perl-Code den aktuellen DP-Algorithmus Implementierung:

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

Normalerweise würde solve() einen rekursiven Aufruf erfordern, sondern weil wir immer versuchen, Werte in der Reihenfolge 0, 1, 2, 3 ..., können wir nur die @_solved Array verwenden, um direkt die Antwort für kleinere Problemgrößen zu erhalten.

Dieser Vorgang dauert 93ms auf meinem PC, den Fall zu lösen, für Stempel 1 Größen, 4, 12, 21 und Umschlaggröße 1000. (Die Antwort lautet 20967.) Eine kompilierte Sprache wird noch schneller sein.

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