Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm chi phí tối thiểu để thuê k công nhân bằng Python

Giả sử chúng ta có một mảng được gọi là chất lượng cho mỗi công nhân khác nhau và có một mảng khác được gọi là tiền lương và giá trị K. Công nhân thứ i có chất lượng [i] và mức lương kỳ vọng tối thiểu [i]. Chúng tôi muốn thuê K công nhân để thành lập một nhóm được trả lương. Khi chúng tôi thuê một nhóm K công nhân, chúng tôi phải trả lương cho họ theo các quy tắc sau:

  • Mỗi công nhân trong nhóm được trả lương phải được trả công theo tỷ lệ chất lượng của họ bằng cách so sánh với những người khác trong nhóm được trả lương.

  • Mọi công nhân trong nhóm được trả lương phải được trả ít nhất mức lương tối thiểu mong đợi của họ.

Chúng tôi phải tìm ra số tiền ít nhất cần thiết để tạo thành một nhóm trả phí thỏa mãn các điều kiện trên.

Vì vậy, nếu đầu vào là chất lượng =[10,22,5], lương =[70,52,30] và K =2, thì đầu ra sẽ là 105.000 vì chúng ta sẽ trả 70 cho công nhân đầu tiên và 35 cho công nhân Công nhân thứ 3.

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

  • qr:=một danh sách mới

  • đối với mỗi cặp (q, w) từ chất lượng và tiền lương, làm

    • insert (w / q, q) vào cuối qr

  • sắp xếp danh sách qr

  • cand:=a new list, csum:=0

  • đối với tôi trong phạm vi từ 0 đến K - 1, hãy thực hiện

    • insert -qr [i, 1] vào heap cand

    • csum:=csum + qr [i, 1]

  • ans:=csum * qr [K - 1, 0]

  • đối với idx trong phạm vi K đến kích thước chất lượng, thực hiện

    • insert -qr [i, 1] vào heap cand

    • csum:=csum + qr [idx, 1] + phần tử hàng đầu khỏi heap cand và xóa nó khỏi heap

    • ans =tối thiểu ans và (csum * qr [idx] [0])

  • trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn 

import heapq
def solve(quality, wage, K):
   qr = []
   for q, w in zip(quality, wage):
      qr.append([w/q, q])
   qr.sort()

   cand, csum = [], 0
   for i in range(K):
      heapq.heappush(cand, -qr[i][1])
      csum += qr[i][1]
   ans = csum * qr[K - 1][0]

   for idx in range(K, len(quality)):
      heapq.heappush(cand, -qr[idx][1])
      csum += qr[idx][1] + heapq.heappop(cand)
      ans = min(ans, csum * qr[idx][0])
   return ans

quality = [10,22,5]
wage = [70,52,30]
K = 2
print(solve(quality, wage, K))

Đầu vào 

[10,22,5], [70,52,30], 2

Đầu ra 

105