Chương trình tìm giá trị lớn nhất trong bài toán cái ba lô không giới hạn số lượng bằng Python

Cho hai danh sách weights, values cùng độ dài và dung lượng capacity. Mỗi vật phẩm có thể lấy số lượng không giới hạn. Tìm giá trị lớn nhất có thể đạt được.

Ví dụ: weights = [1, 2, 3], values = [1, 5, 3], capacity = 5 → 11.

Quy trình giải quyết (Quy hoạch động đệ quy + Memoization)

1. Định nghĩa hàm dp(i, k): giá trị lớn nhất từ vật phẩm i trở đi với dung lượng còn lại k.
2. Nếu i == len(weights), trả về 0.
3. ans = dp(i+1, k) (không lấy vật phẩm i).
4. Nếu k >= weights[i], cập nhật ans = max(ans, dp(i, k - weights[i]) + values[i]) (lấy vật phẩm i).
5. Trả về ans.
6. Gọi dp(0, capacity).

Ví dụ mã nguồn

class Solution:
    def solve(self, weights, values, capacity):
        from functools import lru_cache
        @lru_cache(None)
        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))  # Output: 11

Đầu vào

[1, 2, 3], [1, 5, 3], 5

Đầu ra

11