Verstehen der Implementierung des Bottom-up-Stabes

8

In Einführung in Algorithmen (CLRS) , Cormen et al. Sprechen Sie über das Lösen des Rod-Schneidproblems wie folgt (Seite 369)

%Vor%

Hier ist p[i] der Preis für die Länge des Stabes, r[i] ist der Ertrag, der Stab bei Länge und s[i] zu schneiden, gibt uns die optimale Größe für das erste Stück abzuschneiden.

Meine Frage betrifft die äußere Schleife, die j von 1 bis n iteriert, und die innere Schleife i , die ebenfalls von 1 nach n geht.

In Zeile 6 vergleichen wir q (der bisher maximal erzielte Umsatz) mit r[j - i] , dem maximalen Umsatz, der im vorherigen Schnitt erzielt wurde.

Wenn j = 1 and i = 1 , scheint es in Ordnung, aber die nächste Iteration der inneren Schleife, wo j = 1 and i = 2 , wird nicht r[j - i] be r[1 - 2] = r[-1] ?

Ich bin mir nicht sicher, ob der negative Index hier Sinn macht. Ist das ein Tippfehler in CLRS oder mir fehlt hier etwas?

Ich weiß, dass einige von Ihnen nicht wissen, was das Rod-Cutting-Problem ist, hier ist ein Beispiel .

    
sc_ray 31.03.2011, 22:47
quelle

3 Antworten

8

Hier ist der Schlüssel: for i = 1 to j

i beginnt bei 1 und erhöht den Wert bis zu dem Wert von j .

i wird niemals größer als j sein, daher wird j-i niemals kleiner als Null sein.

    
Unsigned 31.03.2011, 22:51
quelle
0

Die Variable i wird wegen der inneren Schleife nicht größer als die Variable j und somit wird der Index r nie kleiner als Null.

    
Bytemain 31.03.2011 22:55
quelle
0

Sie vermissen die Bedingungen in der inneren for-Schleife. In diesem Fall geht der Wert von i nur bis zu j. Wenn es also j überschreitet, wird die Schleife beendet. Daher keine Frage der negativen Indizes, die Sie erwähnt haben.

    
kpks 19.11.2014 17:17
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Wie stelle ich den PHP-Include-Pfad über .htaccess ein?