Pythonですべてのジョブを完了するための最小時間を見つけるプログラム

jobs [i]がi番目のジョブを完了するために必要な時間を示す、jobsという配列があるとします。また、別の値kがあり、それらにジョブを割り当てることができます。各ジョブは、正確に1人のワーカーに割り当てる必要があります。そして、労働者の労働時間は、彼らに割り当てられたすべての仕事を完了するのにかかる合計時間です。割り当ての可能な限り最小の最大作業時間を見つける必要があります。

したがって、入力がjobs =[2,1,3,8,5]、k =2の場合、出力は10になります。これは、次のようなジョブを割り当てることができるためです。

• ワーカー1：2 + 5 + 3 =10

• ワーカー2：1 + 8 =9

したがって、最大時間は10です。

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

• リストジョブを逆の順序で並べ替えます

• 割り当て：=最初のk個のジョブのリスト

• jobs：=残りのジョブのリスト

• 関数dp（）を定義します。これには私がかかります、割り当てます

• 私が仕事のサイズと同じなら、

  • 割り当ての最大値を返す

• ans：=無限大

• 0からk-1の範囲のxの場合、実行

  • 割り当て：=割り当てからの新しいリスト

  • 割り当て[x]：=割り当て[x]+ジョブ[i]

  • ans：=ansとdp（i + 1、割り当て）の最小値

  • 割り当て[x]：=割り当て[x]-ジョブ[i]

• ansを返す

• メインメソッドからreturndp（0、assign）

例

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

def solve(jobs, k):
   jobs.sort(reverse=True)
   assign = tuple(jobs[:k])
   jobs = jobs[k:]

   def dp(i, assign):
      if i == len(jobs):
         return max(assign)

      ans = float('inf')
      for x in range(k):
         assign = list(assign)
         assign[x] += jobs[i]
         ans = min(ans, dp(i+1, tuple(assign)))
         assign[x] -= jobs[i]

      return ans

   return dp(0, assign)

jobs = [2,1,3,8,5]
k = 2
print(solve(jobs, k))

入力

[2,1,3,8,5], 2

出力

10