Dynamic Programming¶
Dynamic Programming or (DP) is a method for solving complex problems by breaking them down into simpler overlapping subproblems. It is both a mathematical optimization method and a computer programming method. In both contexts, it refers to simplifying a complicated problem by breaking it down into simpler subproblems in a recursive manner.
Characteristics of Dynamic Programming¶
- Overlapping Subproblems: The problem can be broken down into smaller, simpler subproblems which can be further broken down until the result is trivial.
- Optimal Substructure: The optimal solution to the problem contains the optimal solutions to the subproblems.
Dynamic Programming vs Divide and Conquer¶
Both DP and Divide and Conquer (D&C) are powerful problem-solving paradigms, but they have distinct characteristics and are used in different scenarios. Here's a breakdown of their differences:
Nature of Subproblems¶
- Dynamic Programming: Involves breaking down a problem into overlapping subproblems. This means the same subproblem is solved multiple times. The main motivation behind DP is to avoid redundant computations by storing the results of expensive function calls and reusing them when needed.
- Divide and Conquer: Breaks down a problem into distinct (non-overlapping) subproblems. Each subproblem is independent of others. The solutions to the subproblems do not overlap, so there's no need to solve the same problem multiple times.
Storage¶
- Dynamic Programming: Uses additional storage to save the results of subproblems (often in tables or arrays). This is called memoization. This storage is essential because it ensures that each subproblem is computed only once.
- Divide and Conquer: Doesn't necessarily use additional storage for memoization since the same subproblem isn't solved multiple times. However, D&C algorithms, especially recursive ones, might use additional storage in the call stack.
Approach¶
- Dynamic Programming: Can be approached in two ways: top-down (using recursion and memoization) or bottom-up (iteratively filling up a table of solutions). The bottom-up approach starts with the simplest cases and builds up to the desired problem, ensuring that each subproblem is solved before solving the next.
- Divide and Conquer: Typically uses a top-down approach. The problem is divided into smaller subproblems, which are then solved recursively until they reach a base case.
While both DP and D&C break problems down into smaller parts, the key difference lies in the nature of the subproblems (overlapping vs. distinct) and the methodology (memoization vs. pure recursion). Understanding when to use which paradigm is crucial for efficient problem-solving in algorithm design.
Cutting Rod problem¶
Given a rod of length n inches and an array of prices that includes prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if the length of the rod is 8 and the values of different pieces are given as the following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)
length | 1 2 3 4 5 6 7 8
--------------------------------------------
price | 1 5 8 9 10 17 17 20
And if the prices are as follows, then the maximum obtainable value is 24 (by cutting in eight pieces of length 1)
length | 1 2 3 4 5 6 7 8
--------------------------------------------
price | 3 5 8 9 10 17 17 20
def cutRod(price, n):
# val[i] is the maximum value obtainable by cutting up the rod of length i
val = [0 for x in range(n + 1)]
# Create a 2D array to store intermediate max_val values
max_val_array = [[0 for j in range(n)] for i in range(n + 1)]
# Build the val array in a bottom-up manner and return the last entry
# from the val array
for i in range(1, n + 1):
max_val = float("-inf")
for j in range(i):
max_val = max(max_val, price[j] + val[i - j - 1])
max_val_array[i][j] = max_val
val[i] = max_val
# uncommant if you want to print the max_val 2D array
"""
for i in range(1, n + 1):
for j in range(i):
print(max_val_array[i][j], end=" ")
print()
"""
return val[n]
%time
arr = [1, 5, 8, 9, 10, 17, 17, 20]
size = len(arr)
print("Maximum Obtainable Value is", cutRod(arr, size))
CPU times: user 2 µs, sys: 1 µs, total: 3 µs Wall time: 4.53 µs Maximum Obtainable Value is 22
Recursive Solution with memoization¶
def cutRod(price, index, n, memo=None):
# Initialize memoization table if it's not provided
if memo is None:
memo = {}
# Check if the result for this subproblem is already computed
if (index, n) in memo:
return memo[(index, n)]
# Base case
if index == 0:
return n * price[0]
# At any index we have 2 options: either cut the rod of this length or not cut it
notCut = cutRod(price, index - 1, n, memo)
cut = float("-inf")
rod_length = index + 1
if rod_length <= n:
cut = price[index] + cutRod(price, index, n - rod_length, memo)
# Store the result in the memoization table before returning
memo[(index, n)] = max(notCut, cut)
return memo[(index, n)]
%time
arr = [1, 5, 8, 9, 10, 17, 17, 20]
size = len(arr)
print("Maximum Obtainable Value is", cutRod(arr, size - 1, size))
CPU times: user 1 µs, sys: 0 ns, total: 1 µs Wall time: 2.15 µs Maximum Obtainable Value is 22
The Knapsack problem¶
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item $i$ to include in a collection so that the total weight $w$ is less than or equal to a given limit and the total value $v$ is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
As you can see on the animation below it is common to use a 2d array to solve the problem. The rows represent the items and the columns represent the weight of the knapsack. The value of each cell is the maximum value that can be obtained with the given weight and items.
It is well known for its applications in the fields of combinatorics, computer science, complexity theory, cryptography, and many more.
Let's see how we can solve it using dynamic programming.
def knapsack(weights, profits, W):
n = len(weights)
# Initialize our 2d matrix to store the maximum profit for each subproblem
dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
# Build the maximum profit table
for i in range(1, n + 1):
for w in range(1, W + 1):
# If the weight of the current item is less than or equal to w : if our knapsack can hold it
if weights[i-1] <= w:
# Consider the maximum profit by including or excluding the current item
dp[i][w] = max(dp[i-1][w], profits[i-1] + dp[i-1][w-weights[i-1]])
else:
# If the weight of the current item is more than w, then don't include it
dp[i][w] = dp[i-1][w]
# The last cell of the table contains the maximum profit for the entire problem
return dp[-1][-1]
# Example
%time
weights = [10, 20, 30]
profits = [60, 100, 120]
W = 50
print("Maximum profit:", knapsack(weights, profits, W))
CPU times: user 3 µs, sys: 1 µs, total: 4 µs Wall time: 8.11 µs Maximum profit: 220
Recursive Solution with memoization¶
This is called greedy because at each step we choose the item with the highest value per weight. This is not always the optimal solution, that's why we can use recursion with memoization to find the optimal solution 😎
def knapSack(W, wt, val, n, memo=None):
# Initialize memoization table if it's not provided
if memo is None:
memo = [[-1 for _ in range(W + 1)] for _ in range(n + 1)]
# Base Case
if n == 0 or W == 0:
return 0
# Check if the result for this subproblem is already computed
if memo[n][W] != -1:
return memo[n][W]
# If weight of the nth item is more than Knapsack of capacity W,
# then this item cannot be included in the optimal solution
if wt[n-1] > W:
memo[n][W] = knapSack(W, wt, val, n-1, memo)
return memo[n][W]
# Return the maximum of two cases: (1) nth item included, (2) not included
else:
memo[n][W] = max(
val[n-1] + knapSack(W-wt[n-1], wt, val, n-1, memo),
knapSack(W, wt, val, n-1, memo)
)
return memo[n][W]
%time
profit = [60, 100, 120]
weight = [10, 20, 30]
W = 50
n = len(profit)
print(knapSack(W, weight, profit, n))
CPU times: user 2 µs, sys: 0 ns, total: 2 µs Wall time: 1.91 µs 220