Advertisement
WONGDEEM

Untitled

Nov 2nd, 2021
520
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.11 KB | None | 0 0
  1. ## top-down
  2. def dp_memo(n, w_arr, p_arr, weight, dic):
  3.     if n == 0 or weight == 0:
  4.         return 0
  5.     if w_arr[n-1] > weight:
  6.         dic[w_arr[n-1]] = dp_memo(n-1, w_arr, p_arr, weight, dic)
  7.         return dic[w_arr[n-1]]
  8.     else:
  9.         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))
  10.         return dic[n]
  11.  
  12. w = [4,6,8]
  13. p = [7,6,9]
  14. dic = {}
  15. print("Top-down Approach (Memoization)")
  16. print(dp_memo(3, w, p, 14, dic))
  17.  
  18. ## bottom-up
  19. def dp_tab(weight):
  20.     n = 3
  21.     matrix = [[0 for i in range(weight+1)] for j in range(n+1)]
  22.     w = [5,6,8]
  23.     p = [7,6,9]
  24.     def dp(weight, matrix, w_arr, p_arr):
  25.         for i in range(1,n+1):
  26.             for j in range(1, weight+1):
  27.                 if j < w_arr[i-1]:
  28.                     matrix[i][j] = matrix[i-1][j]
  29.                 if j >= w_arr[i-1]:
  30.                     matrix[i][j] = max(matrix[i-1][j], matrix[i][j-w_arr[i-1]]+p_arr[i-1])
  31.     dp(weight, matrix, w, p)
  32.     for i in matrix:
  33.         print(i)
  34.     return matrix[-1][-1]
  35.  
  36.  
  37. print("Bottom-up Approach (Tabulation)")
  38. print(dp_tab(14))
  39.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement