-
Notifications
You must be signed in to change notification settings - Fork 2
Dynamic Programming Problems
Praveen Kumar Anwla edited this page Dec 12, 2024
·
59 revisions
Ans:
def subset_sum(M, nums):
DP = [[False for _ in range(M+1)] for _ in range(len(nums)+1)]
#Initialize the first colum to be True
for i in range(len(nums)+1):
DP[i][0] = True
#Construct the rest of the table
for i in range(1, len(nums)+1):
for j in range(1, M+1):
if j < nums[i-1]: # if local sum value is less than the actual item in the list
DP[i][j] = DP[i-1][j] # Don't include the item in subset; Copy the value from above cell. Since after adding the current item also local sum will be less than subset combined.
else: # if local sum value is not less than the actual item in the list
if DP[i-1][j]: # If above cell value is True
DP[i][j] = DP[i-1][j] # Don't include the item in subset; Copy the value from above cell. Since, the subset sum j can be achieved without including the current number (nums[i-1]). Therefore, simply copy the value from the above cell.
else: # means you cannot achieve the sum j without including the current number. Now check if including the current number helps:
DP[i][j] = DP[i-1][j-nums[i-1]] # # Include the item in subset- Decrement the column index by actual integer. Subtract the current number from j (j - nums[i-1]) and check the cell in the row above (DP[i-1][j-nums[i-1]]). If that cell is True, it means you can achieve the sum j by including the current number.
# Get the subset values which sum upto the desired sum.
j = M
i = len(nums)
while i > 0 or j > 0:
if DP[i][j] == DP[i-1][j]: # If current cell item is same as above cell item.
i = i-1
else:
print('item for the subset: %d' % nums[i - 1])
j = j-nums[i-1] # Decrement the column index by actual integer, and decrement the row index by 1.
i = i-1
M = 12
nums = [1, 2, 4, 6]
subset_sum(M, nums)Ans:
def longest_common_subseq(s1, s2):
DP = [[0 for _ in range(len(s1)+1)] for _ in range(len(s2)+1)]
# This is why Running time complexity = o(m*n)
# m= len(s1), n= len(s2)
# Construct the table
for i in range(1, len(s1)+1):
for j in range(1, len(s2)+1):
# NOte: we're comparing s1[i - 1] & s2[j - 1] at both times
# 1)while creating a memoization table and while backtracking
# coz we've appended 0 in both strings. Hence, i-1 to compare current elements.
if s1[i-1] == s2[j-1]: # if chars are matching
DP[i][j] = DP[i-1][j-1]+1
else:
DP[i][j] = max(DP[i-1][j], DP[i][j-1])
# Retrieve the longest common subsequence
lcs = ''
i, j = len(s1), len(s2)
while i > 0 or j > 0:
if s1[i-1] == s2[j-1]: # if chars are matching then char is part of lcs
lcs += s1[i-1]
# Got to diagonal cell
i -= 1
j -= 1
# if chars are not matching then find larger of 2 cells and go one step in direction of larger one
elif DP[i-1][j] > DP[i][j-1]: # top cell value > left cell value
i -= 1 # go up
else: # left cell value > top cell value
j -= 1 # go left
return print(lcs[::-1])
s1 = "ABCD"
s2 = "ACDF"
longest_common_subseq(s1, s2)Ans:
def rod_cutting(length, Profits):
DP = [[0]*(length+1) for _ in range(len(Profits))]
# Construct the table
for i in range(1, len(Profits)): # starting_range=1 coz 0 is the base
for j in range(1, length+1):
if i <= j: # if current piece length is less than or equal to the length of the rod
DP[i][j] = max(DP[i-1][j], Profits[i]+DP[i][j-i]) ## DP[i-1][j] : excluding current piece
else: # if current piece length is greater than length of the rod, meaning you can't make the cut. Hence, exclude current piece.
DP[i][j] = DP[i-1][j]
i = len(Profits)-1
j = pieces
while i > 0 or j > 0:
if DP[i][j] == DP[i-1][j]: ## if current and top cells are matching then give item is not in solution.
i -= 1 # Hence, descrese i for next iteration
else: # if current and top cells are not matching then take this ; meaning current item is in solution.
print("Take piece with length:", i, "meter")
j = j-i
# Example input
length = 5
Profits = [0, 2, 5, 7, 3, 9]
# Call the function
rod_cutting(pieces, Profit)Output:
- Take piece with length: 2 meter
- Take piece with length: 2 meter
- Take piece with length: 1 meter
Q4. 0/1 Knapsack Problem: you're given a set of items, each with a weight and a value, and your goal is to determine the combination of items to include in a knapsack of limited capacity such that the total value is maximized.
Ans:
def knapsack_prob(N, M, W, V):
DP = [[0 for _ in range(M+1)] for _ in range(N+1)]
for i in range(1, N+1): #For each item i, we have two choices: not_taking_item , taking_item
for w in range(1, M+1):
not_taking_item = DP[i-1][w] # The best value we can have is simply the best value we had without this item, i.e., DP[i-1][w].
taking_item = 0
if W[i] <= w: # Check if current item's weight is less than knapsack's capacity
taking_item = V[i] + DP[i-1][w-W[i]] # value if taking current item;
DP[i][w] = max(not_taking_item, taking_item) # Update DP table
else:
DP[i][w] = not_taking_item
print("Total benefit: %d" % DP[N][M])
w = M
for i in range(N, 0 , -1): # Iterate through all items in DP table in backward direction
# If current weight is not zero, and current and above cell values are not matching
if DP[i][w] != 0 and DP[i][w] != DP[i-1][w]:
print("We're taking item #%d" % i)
w -= W[i] # Decrease the knapsack's capacity, since we've considered this item already
# Example input
num_of_items = 4
knapsack_capacity = 7
weights = [0, 1, 3, 4, 5]
profits = [0, 1, 4, 5, 7]
# Call the function
knapsack_prob(num_of_items, knapsack_capacity, weights, profits)output:
- Total benefit: 9
- We're taking item #3
- We're taking item #2
Q5: Kadane's Algorithm : Find Maximum consecutive Subarray i.e. Find the consecutive numbers of the array such that sum is the largest possible.
Ans:
# O(N)
def kadane(nums):
local_max = nums[0]
global_max = nums[0]
# this is why it has linear running time complexity
for i in range(1, len(nums)):
local_max = max(nums[i], local_max + nums[i])
if local_max > global_max:
global_max = local_max
return global_max
kadane([1, -2, 1, 2, 3, -4])Ans:
# top-down approach
def fibonacci_memoization(n, DP):
if n not in DP:
DP[n] = fibonacci_memoization(n-1, DP) + fibonacci_memoization(n-2, DP)
return DP[n]
# bottom-up approach
def fibonacci_tabulation(n, DP):
for i in range(2, n+1):
DP[i] = DP[i-1] + DP[i-2]
return DP[n]
DP = {0: 1, 1: 1}
print("===== fibonacci_tabulation =====")
print(fibonacci_tabulation(4, DP))
# print("===== fibonacci_memoization =====")
# print(fibonacci_memoization(4, DP))Q7. Search for occurrences of a pattern within a given text. The primary goal is to find all occurrences of a specified pattern in the text using "Knuth–Morris–Pratt (KMP) algorithm.
Ans:
def prepare_pi_table(pattern):
pi_table = [0] * len(pattern)
prefix_counter, i = 0, 1 # i: to iterate through elements of pattern
while i < len(pattern):
if pattern[i] == pattern[prefix_counter]:
pi_table[i] = prefix_counter + 1
i += 1
prefix_counter += 1
else:
if prefix_counter != 0:
prefix_counter = pi_table[prefix_counter - 1]
else:
pi_table[i] = 0
i += 1
return pi_table
def search_for_pattern(text, pattern):
pi_table = prepare_pi_table(pattern)
# i: to track elements in text, j: to track elements in pattern
i, j = 0, 0
while i < len(text) and j < len(pattern):
if text[i] == pattern[j]: # if chars in text and pattern match
i += 1
j += 1
if j == len(pattern): # means if pattern's length is covered then pattern found
print('Pattern found at index %s' % (i - j))
j = pi_table[j - 1]
elif j != 0:
j = pi_table[j - 1]
else:
i += 1
# Example usage
search_for_pattern('abababab', 'aba')output:
- Pattern found at index 0
- Pattern found at index 2
- Pattern found at index 4