Dynamic Programming - 0/1 Knapsack.
Dynamic Programming has two characteristics: 1) overlapping subproblems 2) optimal substructure. Dynamic programming includes two methods: 1) top-down with memoization (recursion) 2) bottom-up with tabulation (no recursion).
1] Top down without memoization.
def Fibonacci(n):
if n < 2:
return n
return Fibonacci(n-1) + Fibonacci(n-2)
2] Top down with memoization.
def Fibonacci(n):
memoize = [-1 for _ in range(n+1)]
return recursion(memoize, n)
def recursion(memoize, n):
if n < 2:
return n
# if the subproblem has been solved
if memoize[n] >= 0:
return memoize[n]
# if the subproblem has not been solved
memoize[n] = recursion(memoize, n-1) + recursion(memoize, n-2)
return memoize[n]
3] Bottom up with tabulation.
def Fibonacci(n):
dp = [0,1]
for i in range(2, n + 1):
dp.append(dp[i-1] + dp[i-2])
return dp[n]
1. 0/1 Knapsack
Given two integer arrays to represent weights and profits of N items, we need to find a subset of these items which will give us maximum profit such that their cumulative weight is not more than a given number C. Write a function that returns the maximum profit. Each item can only be selected once, which means either we put an item in the knapsack or skip it.
1] Brute Force - Recursion.
# Time complexity O(2^N). Space complexity O(N).
def solve_knapsack(profits, weights, capacity):x
return recursion(profits, weights, capacity, 0)
def recursion(profits, weights, capacity, index):
# base
if capacity <=0 or index >= len(profits):
return 0
# recursion call after choosing the element at the index
profit1 = 0
if weights[index] <= capacity:
profit1 = profits[index] + recursion(profits, weights, capacity - weights[index], index + 1)
# recursion call after excluding the element at the index
profit2 = recursion(profits, weights, capacity, index + 1)
return max(profit1, profit2)
2] Top Down Dynamic Programming with Memoization. (recursion)
# Time complexity O(N * C). Space complexity O(N * C). N is the number of items and C is the capacity.
def solve_knapsack(profits, weights, capacity):
dp = [[-1 for _ in range(capacity + 1)] for _ in range(len(profits))]
return recursion(dp, profits, weights, capacity, 0)
def recursion(dp, profits, weights, capacity, index):
# base
if capacity <= 0 or index >= len(profits):
return 0
# recursion call after choosing the element at the index
profit1 = 0
if weights[index] <= capacity:
profit1 = profits[index] + recursion(dp, profits, weights, capacity - weights[index], index + 1)
# recursion call after excluding the element at the index
profit2 = recursion(dp, profits, weights, capacity, index + 1)
dp[index][capacity] = max(profit1, profit2)
return dp[index][capacity]
3] Bottom Up Dynamic Programming. (Optimal solution will be the maximum of the following two values dp[i][c] = max(dp[i-1][c], profits[i] + dp[i-1][c - weights[i]]))
# Time complexity O(N * C). Space complexity O(N * C).
def solve_knapsack(profits, weights, capacity):
# base
n = len(profits)
if capacity <= 0 or n == 0 or len(weights) != n:
return 0
dp = [[0 for _ in range(capacity + 1)] for _ in range(n)]
# populate the capacity = 0 columns with 0 profits
for i in range(n):
dp[i][0] = 0
# populate the first row with the corresponding profit if the weight does not exceed the capacity
for c in range(capacity + 1):
if weights[0] <= c:
dp[0][c] = profits[0]
# process all sub array for all the capacities
for i in range(1,n):
for c in range(1, capacity + 1):
profit1, profit2 = 0, 0
# include the item, if it is not more than the capacity
if weights[i] <= c:
profit1 = profits[i] + dp[i-1][c - weights[i]]
# exclude the item
profit2 = dp[i-1][c]
# take the maximum
dp[i][c] = max(profit1, profit2)
# maximum profit will be at the right bottom corner
return dp[n-1][capacity]
Reduce the space complexity to O(C).
def solve_knapsack(profits, weights, capacity):
# base
n = len(profits)
if capacity <= 0 or n == 0 or len(weights) != n:
return 0
dp = [0 for _ in range(capacity + 1)]
for c in range(capacity + 1):
if weights[0] <= c:
dp[c] = profits[0]
for i in range(1, n):
for c in range(capacity, -1, -1): # reverse order
profit1, profit2 = 0, 0
# include the item
if weights[i] <= c:
profit1 = profits[i] + dp[c - weights[i]]
# exclude the item
profit2 = dp[c]
# choose the maximum
dp[c] = max(profit1, profit2)
return dp[capacity]
2. Equal Subset Sum Partition
Given a set of positive numbers, find if we can partition it into two subsets such that the sum of elements in both the subsets is equal.
1] Brute Force Recursion. Assume the total number of all the given numbers is ‘S’, then the two equal subsets must have.a sum equal to ‘S/2’. So we turn t o find a subset of teh given numbers that has a total sum of ‘S/2’.
# Time complexity O(2^N). Space complexity O(N)
def can_partition(num):
SUM = sum(num)
# SUM cannot be an odd number, otherwise two subsets cannot have equal sum.
if SUM % 2 != 0:
return False
return recursive(num, SUM / 2, 0)
def recursive(num, SUM, index):
# base
if SUM == 0:
return True
n = len(num)
if n == 0 or index >= n:
return False
# recursive call after choosing the number at the index
if num[index] <= SUM:
if recursive(num, SUM - num[index], index + 1):
return True
# recursive all after excluding teh number at the index
return recursive(num, SUM, index + 1)
2] Top-down Dynamic Programming with Memoization.
