Advertisement

# 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