Pythonでk人の労働者を雇うための最小コストを見つけるためのプログラム

異なるワーカーごとにqualityという配列があり、wagesと値Kという別の配列があるとします。i番目のワーカーには、quality[i]と最低賃金期待賃金[i]があります。有給のグループを形成するためにK人の労働者を雇いたい。 K人の労働者のグループを雇用する場合、次の規則に従って彼らに支払う必要があります。

• 有給グループの各労働者は、有給グループの他の労働者と比較することにより、質の比率で支払われるべきです。

• 有給グループのすべての労働者は、少なくとも最低賃金の期待を支払わなければなりません。

上記の条件を満たす有料グループを形成するために必要な最小限の金額を見つける必要があります。

したがって、入力が品質=[10,22,5]、賃金=[70,52,30]、K =2のような場合、最初の労働者に70を支払い、 3人目の労働者。

これを解決するには、次の手順に従います-

• qr：=新しいリスト

• 品質と賃金からの各ペア（q、w）について、実行します

  • qrの最後に（w / q、q）を挿入します

• リストを並べ替えるqr

• cand：=新しいリスト、csum：=0

• 0からK-1の範囲のiの場合、実行

  • -qr [i、1]をヒープカンドに挿入します

  • csum：=csum + qr [i、1]

• ans：=csum * qr [K-1、0]

• Kから品質のサイズまでの範囲のidxについては、実行してください

  • -qr [i、1]をヒープカンドに挿入します

  • csum：=csum + qr [idx、1]+ヒープカンドの最上位要素をヒープから削除します

  • ans =ansの最小値および（csum * qr [idx] [0]）

• ansを返す

例

理解を深めるために、次の実装を見てみましょう

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