Advertisement
WONGDEEM

Untitled

Nov 2nd, 2021
498
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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[i-1]:
  28.                     matrix[i][j] = max(matrix[i-1][j], matrix[i][j+1-w[i-1]]+p[i-1])
  29.     dp(weight, matrix, w, p)
  30.     for i in matrix:
  31.         print(i)
  32.     return matrix[-1][-1]
  33.  
  34.  
  35. print("Bottom-up Approach (Tabulation)")
  36. print(dp_tab(14))
  37.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement