Chương trình tìm giá trị lớn nhất khi chọn đồ vật vào balo trong Python

Cho 2 danh sách weights, values cùng độ dài, và capacity (trọng lượng tối đa), count (số vật tối đa). Mỗi vật chỉ chọn tối đa 1 lần. Tìm giá trị lớn nhất.

Ví dụ: weights=[2,2,4,6], values=[15,15,20,35], capacity=8, count=3 → 50 (chọn 3 vật đầu).

Giải thuật (Đệ quy DP - Knapsack 0/1 với giới hạn số lượng)

Hàm dp(i, cp, ct): xét từ vật i, dung lượng còn cp, còn chọn được ct vật.

• Cơ sở: i == n hoặc ct == 0 → 0.
• Không chọn vật i: ans = dp(i+1, cp, ct).
• Chọn vật i (nếu cp >= w): ans = max(ans, dp(i+1, cp-w, ct-1) + v).

Lưu ý: Cần memoization để tránh tính lặp (tốn O(n * capacity * count)).

Ví dụ minh họa

from functools import lru_cache

class Solution:
    def solve(self, weights, values, capacity, count):
        items = list(zip(weights, values))
        
        @lru_cache(None)
        def dp(i, cp, ct):
            if i == len(items) or ct == 0:
                return 0
            w, v = items[i]
            ans = dp(i + 1, cp, ct)
            if cp >= w:
                ans = max(ans, dp(i + 1, cp - w, ct - 1) + v)
            return ans
        
        return dp(0, capacity, count)

ob = Solution()
weights = [2, 2, 4, 6]
values = [15, 15, 20, 35]
capacity = 8
count = 3
print(ob.solve(weights, values, capacity, count))  # Output: 50

Đầu vào / Đầu ra

Input: [2,2,4,6], [15,15,20,35], 8, 3

Output: 50