Maximierung der Anzahl verschiedener Zahlen, die eine gegebene Summe 'k' ergeben
Ich brauche Hilfe bei diesem Problem der dynamischen Programmierung.
Geben Sie für eine positive ganze Zahl
kdie maximale Anzahl von eindeutigen positiven Ganzzahlen an, die sich zukaddieren. Zum Beispiel: 6 = 1 + 2 + 3, also wäre die Antwort 3, im Gegensatz zu 5 + 1 oder 4 + 2, was 2 wäre.
Das erste, woran ich denke, ist, dass ich ein Teilproblem finden muss. Um also die maximale Summe für k zu finden, müssen wir die maximale Summe für die Werte finden, die kleiner als k sind. Also müssen wir die Werte 1 -> k durchlaufen und die maximale Summe für diese Werte finden.
Was mich verwirrt, ist, wie man eine Formel macht. Wir können M(j) als die maximale Anzahl unterschiedlicher Werte definieren, die sich zu j addieren, aber wie schreibe ich die Formel dafür?
Ist meine Logik für das, was ich bisher richtig verstanden habe, und kann jemand erklären, wie man Schritt für Schritt vorgeht?
6 Antworten
Es ist keine dynamische Programmierung erforderlich. Beginnen wir mit einem Beispiel:
%Vor%Neun Zahlen sind so weit wie möglich. Wenn wir zehn Zahlen verwenden, wäre die Summe mindestens 1 + 2 + 3 + ... + 10 = 55, was größer als 50 ist - also ist es unmöglich.
In der Tat, wenn wir genau n verschiedene positive ganze Zahlen verwenden, dann ist die niedrigste Zahl mit einer solchen Summe 1 + 2 + ... + n = n ( n +1) / 2. Durch Lösen der Quadratischen haben wir, dass M ( k ) ungefähr sqrt (2
Also soll der Algorithmus die Zahl k nehmen, 1, 2, 3, usw. subtrahieren, bis wir nicht mehr können, dann um 1 dekrementieren. Algorithmus in C:
%Vor%Die anderen Antworten ergeben richtigerweise, dass das Problem im Wesentlichen diese Summe ist:
Dies kann jedoch tatsächlich zu
vereinfacht werden
Im Code sieht das so aus: floor(sqrt(2.0 * k + 1.0/4) - 1.0/2)
Der Nachteil dieser Antwort ist, dass Sie mit Fließkommazahlen umgehen müssen.
Brian M. Scott ( Ссылка ), Gegeben eine positive ganze Zahl, finde die maximal eindeutigen positiven ganzen Zahlen, die ihre Summe bilden können, URL (Version: 2012-03-22): Ссылка
Die kleinste Zahl, die als Summe von i verschiedenen positiven ganzen Zahlen dargestellt werden kann, ist 1 + 2 + 3 + ... + i = i(i+1)/2 , sonst bekannt als i 'th Dreieckszahl, T[i] .
Lassen Sie i so aussehen, dass T[i] die größte Dreieckszahl ist, die kleiner oder gleich Ihrer k ist.
Dann können wir k als Summe von i verschiedenen positiven ganzen Zahlen darstellen:
Beachten Sie, dass der letzte Ausdruck größer oder gleich i ist (und sich daher von den anderen Ganzzahlen unterscheidet), da k >= T[i] .
Es ist auch nicht möglich, k als Summe von i+1 verschiedenen positiven ganzen Zahlen darzustellen, da die kleinste Zahl, die die Summe von i+1 verschiedenen positiven ganzen Zahlen ist, T[i+1] > k ist, weil wir i gewählt haben .
Ihre Frage entspricht also dem Finden der größten i , also T[i] <= k .
Das ist gelöst:
%Vor%[Ableitung hier: Ссылка ]
Sie könnten auch ein einfaches Programm schreiben, um durch die dreieckigen Zahlen zu iterieren, bis Sie die erste größer als k finden:
%Vor% Ich denke, Sie überprüfen nur, ob 1 + ... + n > k . Wenn ja, drucke n-1 .
Weil, wenn Sie die kleinste n als 1 + ... + n > k finden, dann 1 + ... + (n-1) <= k . Fügen Sie also den zusätzlichen Wert, sagen E , zu (n-1) , dann 1 + ... + (n-1+E) = k .
Daher ist n-1 das Maximum.
%Vor%Beachten Sie, dass: 1 + ... + n = n (n + 1) / 2
Oder Sie können M(j) machen.
Nun, das Problem könnte ohne dynamische Programmierung gelöst werden, aber ich habe versucht, es in dynamischer Programmierung zu betrachten.
Tipp: Wenn Sie ein dynamisches Programmierproblem lösen wollen, sollten Sie sehen, wenn sich die Situation "wiederholt". Hier ist es vom Standpunkt der Zahl k aus egal, ob ich zum Beispiel 1 zuerst und dann 3 oder zuerst 3 und dann 1 subtrahiere; Ich sage "lasst uns in aufsteigender Reihenfolge davon abziehen". Nun, was wird wiederholt? Ok, die Idee ist, dass ich mit der Zahl k beginnen und sie von verschiedenen Elementen subtrahieren will, bis ich auf Null komme. Wenn ich also zu einer Situation komme, in der die verbleibende Nummer und die letzte eindeutige Nummer, die ich benutzt habe, gleich sind, wird die Situation "wiederholt":
%Vor%Die Zeitkomplexität ist O (k ^ 3)
Obwohl es nicht ganz klar ist, welche Einschränkungen es gibt, wie Sie zu Ihrer größten diskreten Reihe von Zahlen kommen, aber wenn Sie dazu in der Lage sind, übergeben Sie ein einfaches Array, um die diskreten Zahlen zu halten und eine laufende Summe zu halten Funktionen können den Prozess vereinfachen. Wenn Sie beispielsweise das Array a long mit Ihrer aktuellen j an die Funktion übergeben und die Anzahl der Elemente, die die Summe innerhalb des Arrays ausmachen, zurückgeben, können Sie Folgendes tun:
Das Zusammenstellen in einem kurzen Testprogramm würde wie folgt aussehen:
%Vor%Beispiel Verwendung / Ausgabe
%Vor%Ich entschuldige mich, wenn ich irgendwo eine Einschränkung bei der Auswahl der diskreten Werte verpasst habe, aber wenn man sich auf diese Weise nähert, erhält man garantiert die größte Anzahl diskreter Werte, die Ihrer Summe entsprechen. Lass es mich wissen, wenn du Fragen hast.
Tags und Links algorithm c dynamic-programming