Python-Programm zum Schneiden einer Stange | DP-13
Gegeben sei ein Stab der Länge n Zoll und ein Array von Preisen, das die Preise aller Stücke mit einer Größe kleiner als n enthält. Ermitteln Sie den maximal erzielbaren Wert, indem Sie die Rute zerschneiden und die Stücke verkaufen. Wenn zum Beispiel die Länge der Stange 8 ist und die Werte der verschiedenen Teile wie folgt angegeben sind, dann ist der maximal erreichbare Wert 22 (durch Schneiden in zwei Teile der Längen 2 und 6)
length | 1 2 3 4 5 6 7 8 -------------------------------------------- price | 1 5 8 9 10 17 17 20
Und wenn die Preise wie folgt sind, dann ist der maximal erreichbare Wert 24 (durch Schneiden in acht Stücke der Länge 1)
length | 1 2 3 4 5 6 7 8 -------------------------------------------- price | 3 5 8 9 10 17 17 20
Es folgt eine einfache rekursive Implementierung des Rod-Cutting-Problems. Die Implementierung folgt einfach der oben erwähnten rekursiven Struktur.
Python
# A Naive recursive solution # for Rod cutting problem import sys # A utility function to get the # maximum of two integers def max(a, b): return a if (a > b) else b # Returns the best obtainable price for a rod of length n # and price[] as prices of different pieces def cutRod(price, n): if(n <= 0): return 0 max_val = -sys.maxsize-1 # Recursively cut the rod in different pieces # and compare different configurations for i in range(0, n): max_val = max(max_val, price[i] + cutRod(price, n - i - 1)) return max_val # Driver code arr = [1, 5, 8, 9, 10, 17, 17, 20] size = len(arr) print("Maximum Obtainable Value is", cutRod(arr, size)) # This code is contributed by 'Smitha Dinesh Semwal'
Der maximal erreichbare Wert beträgt 22
Unter Berücksichtigung der obigen Implementierung folgt ein Rekursionsbaum für einen Stab der Länge 4.
cR() ---> cutRod() cR(4) / / / / cR(3) cR(2) cR(1) cR(0) / | / | / | / | cR(2) cR(1) cR(0) cR(1) cR(0) cR(0) / | | / | | cR(1) cR(0) cR(0) cR(0) / / CR(0)
Im obigen partiellen Rekursionsbaum wird cR(2) zweimal gelöst. Wir sehen, dass es viele Teilprobleme gibt, die immer wieder gelöst werden. Da dieselben Teilprobleme erneut aufgerufen werden, hat dieses Problem die Eigenschaft Überlappende Teilprobleme. Das Rod-Cutting-Problem hat also beide Eigenschaften (siehe this und this ) eines dynamischen Programmierproblems. Wie bei anderen typischen Problemen der dynamischen Programmierung (DP) können Neuberechnungen derselben Unterprobleme vermieden werden, indem ein temporäres Array val[] von unten nach oben erstellt wird.
Python
# A Dynamic Programming solution for Rod cutting problem INT_MIN = -32767 # Returns the best obtainable price for a rod of length n and # price[] as prices of different pieces def cutRod(price, n): val = [0 for x in range(n + 1)] val[0] = 0 # Build the table val[] in bottom up manner and return # the last entry from the table for i in range(1, n + 1): max_val = INT_MIN for j in range(i): max_val = max(max_val, price[j] + val[i-j-1]) val[i] = max_val return val[n] # Driver program to test above functions arr = [1, 5, 8, 9, 10, 17, 17, 20] size = len(arr) print("Maximum Obtainable Value is " + str(cutRod(arr, size))) # This code is contributed by Bhavya Jain
Der maximal erreichbare Wert beträgt 22
Bitte lesen Sie den vollständigen Artikel über das Schneiden einer Stange | DP-13 für mehr Details!