Chương trình thực hiện bài toán gói phân số trong Python

Giả sử chúng ta có hai danh sách, trọng số và giá trị có cùng độ dài và dung lượng giá trị khác. Trọng số [i] và giá trị [i] thể hiện trọng lượng và giá trị của phần tử thứ i. Vì vậy, nếu chúng ta có thể lấy tối đa trọng lượng công suất và chúng ta có thể lấy một phần trọng lượng của một mặt hàng với giá trị tương ứng, chúng ta phải tìm lượng giá trị lớn nhất mà chúng ta có thể nhận được (làm tròn xuống số nguyên gần nhất)

Vì vậy, nếu đầu vào giống như weights =[6, 7, 3] giá trị =[110, 120, 2] dung lượng =10, thì đầu ra sẽ là 178.

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

• res:=0

  • tạo danh sách các cặp P có trọng số và giá trị, đồng thời sắp xếp chúng dựa trên giá trị trên mỗi trọng số

  • đối với mỗi cặp trong P, thực hiện

    • cif dung lượng bằng 0 thì

      • đi ra từ vòng lặp

    • nếu cặp [0]> dung lượng, thì

      • res:=res + thương số của (cặp [1] / (cặp [0] / dung lượng)

      • công suất:=0

    • ngược lại khi cặp [0] <=dung lượng thì

      • res:=res + cặp [1]

      • dung lượng:=công suất - cặp [0]

  • trả về giá trị sàn của res

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):
      res = 0
      for pair in sorted(zip(weights, values), key=lambda x: - x[1]/x[0]):
         if not bool(capacity):
            break
         if pair[0] > capacity:
            res += int(pair[1] / (pair[0] / capacity))
            capacity = 0
         elif pair[0] <= capacity:
            res += pair[1]
            capacity -= pair[0]
      return int(res)

ob = Solution()
weights = [6, 7, 3]
values = [110, 120, 2]
capacity = 10
print(ob.solve(weights, values, capacity))

Đầu vào

[6, 7, 3],[110, 120, 2],10

Đầu ra

230