Dynamisk programmering i Python

Jag kommer att lösa tre problem med hjälp av dynamisk programmering (DP) i denna handledning. Dynamisk programmering är en teknik som används i matematik och programmering för att snabbt lösa komplexa problem. Ett DP-problem löses genom att dela upp det i delproblem, varje delproblem löses en gång och lösningar på delproblem lagras för att kunna hämtas senare.

Ett dynamiskt programmeringsproblem måste ha en optimal understruktur och överlappande delproblem. Ett problem med icke-överlappande delproblem löses vanligtvis med en splittring-och-erövringsstrategi istället för DP. Ett problem har en optimal understruktur om lösningen kan hittas genom att kombinera optimala lösningar till delproblem. Ett problem med överlappande delproblem har delproblem som måste lösas flera gånger innan den optimala lösningen kan hittas, lösningar på överlappande delproblem kan lagras och återanvändas för att spara tid och göra koden snabbare.

DP-metoden uppfanns 1953 av Richard Bellman och har till exempel tillämpningar inom matematik, teknik och bioinformatik. Dynamisk programmering är baserad på en Bellman-ekvation, det är en tillståndsvärdesfunktion som används för att maximera värdet på nästa tillstånd givet det aktuella tillståndet.

Fibonacci-sekvens

Det här problemet handlar om att generera en sekvens av fibonaccital, funktionen tar sekvensens storlek som indata. Varje genererat fibonaccital sparas i en lista och kan återanvändas senare, resultatet från en körning visas nedanför koden.

# Generate a fibonacci sequence
def fibonacci_sequence(n:int) -> []:

    # Create an array
    numbers = []

    # Loop n numbers
    for i in range(n):
        if i < 2:
            numbers.append(i)
        else:
            numbers.append(numbers[i - 2] + numbers[i - 1])

    # Return fibonacci numbers
    return numbers

# The main entry point for this module
def main():

    # Generate a fibonacci sequence
    print('Fibonacci sequence, {0} numbers: {1}'.format(20, fibonacci_sequence(20)))
    print()

# Tell python to run main method
if __name__ == '__main__': main()

Fibonacci sequence, 30 numbers: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229]

Längsta ökande subsekvens

Detta problem handlar om att hitta den längsta ökande subsekvensen av siffror givet en sekvens av nummer. Algoritmen tar varje nummer i ordning och lägger till det i en subsekvens, ett nummer som uppkommer i inmatningslistan kan inte läggas till före ett redan tillagt nummer. Resultatet från en körning visas nedanför koden.

# Import libraries
import numpy as np

# Get longest increasing subsequence
def get_lis(sequence:[]) -> []:

    # Variables
    n = len(sequence) 
    max_length = 0
    lis = np.ones(n, dtype='int')

    # Get lis lengths
    for i in range (1 , n): 
        for j in range(0 , i): 
            if sequence[i] > sequence[j] and lis[i] < lis[j] + 1 : 
                lis[i] = lis[j]+1
  
    # Get the maximum length
    for i in range(n): 
        max_length = max(max_length, lis[i]) 
  
    # Return the solution
    return max_length

# The main entry point for this module
def main():

    # Generate longest increasing subsequence
    print('Longest increasing subsequence: {0}'.format(get_lis([10, 22, 9, 33, 21, 50, 41, 60, 80])))
    print()

# Tell python to run main method
if __name__ == '__main__': main()

Longest increasing subsequence: 6

Ryggsäckproblem

Det här problemet handlar om att optimera värdet på saker packade i en ryggsäck, detta med hänsyn tagen till den totala vikten. Ryggsäcken kan hantera en viss vikt och du har ett antal saker som du vill packa i ryggsäcken. Målet är att hitta det maximala värdet för sakerna i ryggsäcken, resultatet från en körning visas nedanför koden.

# Get a knapsack solution
def knapsack(max_weight:int, weights:[], values:[]) -> int:

    # Get the length
    n = len(weights)

    # Create a matrix
    matrix = [[0 for w in range(max_weight + 1)] for i in range(n + 1)]

    # Loop max weight
    for w in range(max_weight + 1):

        # Loop all weights and values
        for i in range(n + 1):

            # Add value to matrix
            if (w == 0 or i == 0):
                matrix[i][w] = 0
            elif weights[i-1] <= w:
                matrix[i][w] = max(values[i-1] + matrix[i-1][w-weights[i-1]], matrix[i-1][w])
            else:
                matrix[i][w] = matrix[i-1][w]

    # Return best value
    return matrix[n][max_weight]

# The main entry point for this module
def main():

    # Solve knapsack problem
    print('Best value in knapsack: {0}'.format(knapsack(15, [3,2,4,6,8], [30,20,40,60,80])))
    print()

# Tell python to run main method
if __name__ == '__main__': main()

Best value in knapsack: 150