Chương trình tìm giá trị lớn nhất lấy được từ các vật phẩm trong giới hạn trọng lượng trong Python

Cho hai danh sách weights và values cùng độ dài và một số capacity. weights[i] và values[i] là trọng lượng và giá trị của vật phẩm thứ i. Chỉ được lấy tối đa một lần mỗi vật phẩm và tổng trọng lượng không vượt quá capacity. Tìm giá trị lớn nhất có thể đạt được.

Ví dụ, weights = [2, 3, 4], values = [2, 6, 4], capacity = 6, đầu ra là 8.

Các bước giải quyết (quy hoạch động 0/1 knapsack):

• n := độ dài weights.
• Tạo ma trận dp kích thước (n+1) x (capacity+1) khởi tạo 0.
• Duyệt i từ 0 đến n, j từ 0 đến capacity:
  • Nếu i == 0 hoặc j == 0: dp[i][j] = 0.
  • Ngược lại nếu weights[i-1] <= j: dp[i][j] = max(dp[i-1][j-weights[i-1]] + values[i-1], dp[i-1][j]).
  • Ngược lại: dp[i][j] = dp[i-1][j].
• Trả về dp[n][capacity].

Ví dụ minh họa

class Solution:
    def solve(self, weights, values, capacity):
        n = len(weights)
        dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
        for i in range(n + 1):
            for j in range(capacity + 1):
                if i == 0 or j == 0:
                    dp[i][j] = 0
                elif weights[i-1] <= j:
                    dp[i][j] = max(dp[i-1][j-weights[i-1]] + values[i-1], dp[i-1][j])
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[n][capacity]

ob = Solution()
weights = [2, 3, 4]
values = [2, 6, 4]
capacity = 6
print(ob.solve(weights, values, capacity))

Đầu vào

[2, 3, 4], [2, 6, 4], 6

Đầu ra

8