Giả sử chúng ta có hai danh sách cùng độ dài, chúng được gọi là trọng số và giá trị, và chúng ta cũng có một dung lượng giá trị khác. Ở đây trọng số [i] và giá trị [i] đại diện cho trọng lượng và giá trị của mục thứ i. Nếu chúng tôi có thể lấy tối đa trọng lượng dung lượng và chúng tôi có thể lấy bất kỳ số lượng bản sao nào cho mỗi mục, chúng tôi phải tìm lượng giá trị lớn nhất mà chúng tôi có thể nhận được.
Vì vậy, nếu đầu vào giống như weights =[1, 2, 3], giá trị =[1, 5, 3], dung lượng =5, thì đầu ra sẽ là 11
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Định nghĩa một hàm dp (). Điều này sẽ mất tôi, k
- nếu tôi giống với kích thước của trọng lượng, thì
- trả về 0
- ans:=dp (i + 1, k)
- nếu k> =weights [i], thì
- ans:=tối đa ans và dp (i, k - weights [i]) + giá trị [i]
- trả lại ans
- Từ phương thức chính, hãy làm như sau -
- trả về dp (0, dung lượng)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution: def solve(self, weights, values, capacity): def dp(i, k): if i == len(weights): return 0 ans = dp(i + 1, k) if k >= weights[i]: ans = max(ans, dp(i, k - weights[i]) + values[i]) return ans return dp(0, capacity) ob = Solution() weights = [1, 2, 3] values = [1, 5, 3] capacity = 5 print(ob.solve(weights, values, capacity))
Đầu vào
[1, 2, 3], [1,5,3], 5
Đầu ra
11