Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ## top-down
- def dp_memo(n, w_arr, p_arr, weight, dic):
- if n == 0 or weight == 0:
- return 0
- if w_arr[n-1] > weight:
- dic[w_arr[n-1]] = dp_memo(n-1, w_arr, p_arr, weight, dic)
- return dic[w_arr[n-1]]
- else:
- dic[n] = max(p[n-1]+dp_memo(n, w_arr, p_arr, weight-w[n-1], dic),dp_memo(n-1, w_arr, p_arr, weight, dic))
- return dic[n]
- w = [4,6,8]
- p = [7,6,9]
- dic = {}
- print("Top-down Approach (Memoization)")
- print(dp_memo(3, w, p, 14, dic))
- ## bottom-up
- def dp_tab(weight):
- n = 3
- matrix = [[0 for i in range(weight+1)] for j in range(n+1)]
- w = [5,6,8]
- p = [7,6,9]
- def dp(weight, matrix, w_arr, p_arr):
- for i in range(1,n+1):
- for j in range(1, weight+1):
- if j < w_arr[i-1]:
- matrix[i][j] = matrix[i-1][j]
- if j >= w_arr[i-1]:
- matrix[i][j] = max(matrix[i-1][j], matrix[i][j-w_arr[i-1]]+p_arr[i-1])
- dp(weight, matrix, w, p)
- for i in matrix:
- print(i)
- return matrix[-1][-1]
- print("Bottom-up Approach (Tabulation)")
- print(dp_tab(14))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement