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'
Ausgabe:

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
Ausgabe:
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!