โปรแกรมหาค่าใช้จ่ายน้อยที่สุดในการจ้างงาน k คนใน Python

มีอาร์เรย์ quality และ wage สำหรับแต่ละคน จ้าง K คน โดยจ่ายเงินเดือน:

• อัตราส่วนตาม quality
• ทุกคนได้อย่างน้อย wage[i]

หาเงินรวมน้อยที่สุด

ตัวอย่าง: quality=[10,22,5], wage=[70,52,30], K=2 ผลลัพธ์ 105.0 (จ้างคน 1 และ 3 จ่าย 70 และ 35)

วิธีแก้ปัญหา (Greedy + Heap)

1. คำนวณ ratio = wage/quality เรียงตาม ratio
2. เลือก K คนแรก ใช้ max-heap เก็บ quality
3. ลองแทนที่คนใน heap ด้วยคนถัดไป คำนวณค่าใช้จ่ายใหม่
4. เก็บค่าต่ำสุด

ตัวอย่างโค้ด

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))

อินพุต

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

เอาต์พุต

105