Dynamic Programming

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems, storing the results of those subproblems to avoid redundant work. It is particularly useful for optimization problems where the solution can be expressed as a combination of solutions to subproblems.

Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. The nth Fibonacci number can be calculated using dynamic programming to avoid redundant calculations.

1
2
3
4
5
6
7
8
9
10
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]
# Example usage:
n = 10  # Calculate the 10th Fibonacci number
print(f"The {n}th Fibonacci number is: {fibonacci(n)}")

0-1 Knapsack Problem

The 0-1 Knapsack problem is a classic optimization problem where you have a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity. The goal is to determine the maximum value that can be put in the knapsack without exceeding the weight capacity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]

# Example usage:
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print(f"The maximum value in the knapsack is: {knapsack(weights, values, capacity)}")
1
2
3
4
5
6
7
8
9
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        for j in range(capacity, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

    return dp[capacity]

Complete Knapsack Problem

Complete Knapsack problem is a variation of the 0-1 Knapsack problem where you can use an unlimited number of each item. The dynamic programming approach is similar, but we iterate through the weights in a different order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def complete_knapsack(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        for j in range(weights[i], capacity + 1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

    return dp[capacity]

# Example usage:
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print(f"The maximum value in the complete knapsack is: {complete_knapsack(weights, values, capacity)}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def complete_knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity +1) for _ in range(n)]

    for i in range(n):
        for j in range(1, capacity + 1):
            if weights[i] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i][j - weights[i]] + values[i])
            else:
                dp[i][j] = dp[i-1][j]
            
    return dp[n-1][capacity]

# Example usage:
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print(f"The maximum value in the complete knapsack is: {complete_knapsack(weights, values, capacity)}")