Chương trình tìm số tiền tối đa mà chúng ta có thể nhận được bằng cách lấy các mục khác nhau trong khả năng bằng Python

Giả sử chúng ta có hai danh sách được gọi là trọng số và giá trị có cùng độ dài và một số khác được gọi là dung lượng k. Ở đây trọng số [i] và giá trị [i] hiển thị trọng lượng và giá trị của mục thứ i. Bây giờ, chúng tôi có thể lấy tối đa k trọng lượng dung lượng và chúng tôi chỉ có thể lấy nhiều nhất một bản sao của 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 =[2, 3, 4], giá trị =[2, 6, 4], dung lượng =6, thì đầu ra sẽ là 8

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của quả cân
• dp:=ma trận có dung lượng kích thước x n và điền bằng 0
• đối với tôi trong phạm vi từ 0 đến n, thực hiện
  • đối với j trong phạm vi 0 đến dung lượng, thực hiện
    • nếu tôi giống 0 hoặc j giống 0, thì
      • dp [i, j]:=0
    • ngược lại khi trọng số [i-1] <=j, thì
      • dp [i, j] =tối đa của (dp [i-1, j-weights [i - 1]] + giá trị [i-1]) và (dp [i-1, j])
    • nếu không,
      • dp [i, j]:=dp [i-1, j]
• trả về dp [n, 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):
      n=len(weights)
      dp=[[0 for i 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