PythonでD日以内にパッケージを発送する能力

D日以内にある港から別の港に出荷されるパッケージをコンベヤーベルトに持っていると仮定します。ここで、コンベヤーベルトのi番目のパッケージの重量はweights[i]です。毎日、ベルトに荷物を積んで船に積み込みます。船の最大耐荷重を超える重量を積載することはありません。コンベヤーベルト上のすべてのパッケージがD日以内に出荷されるようになる、船の最小重量容量を見つける必要があります。したがって、入力が[3,2,2,4,1,4]のようで、D =3の場合、出力は6になります。これは、6の出荷容量が、3日間ですべてのパッケージを出荷するための最小値であるためです。 −

• 1日目：3、2

• 2日目、2、4

• 3日目：1、4

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

• 再帰関数solve（）を定義します。これは、重み配列、maxWeight、および船の配列を取ります。これは、-

  のように機能します。

• インデックス：=0

• 0から船の配列の長さまでの範囲のiの場合

  • 船[i]：=0

  • 一方、インデックス<ウェイトと出荷の長さ[i]+ウェイト[インデックス]<=maxWeight

    • 船[i]：=船[i]+重み[インデックス]

    • インデックスを1増やします

• index =重みの長さの場合はtrueを返し、それ以外の場合はfalseを返します

• 主な方法は次のように機能します

• 出荷：=Dと同じサイズの配列で、0で埋めます

• maxWeight：=重みの最大値

• low：=maxWeight、high：=maxWeight+ウェイト配列の長さ+1

• 低<高

  • 中：=低+（高-低）/ 2

  • Solve（weights、mid、ships）がtrueの場合、high：=mid、それ以外の場合、low：=mid + 1

• ハイに戻る

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

例

class Solution(object):
   def shipWithinDays(self, weights, D):
      ships = [0 for i in range(D)]
      max_w = max(weights)
      low = max_w
      high = max_w * len(weights)+1
      while low<high:
         mid = low + (high-low)//2
         if self.solve(weights,mid,ships):
            high = mid
         else:
            low = mid+1
      return high
   def solve(self,weights,max_w,ships):
      index = 0
      for i in range(len(ships)):
         ships[i] = 0
         while index < len(weights) and ships[i]+weights[index]<= max_w:
            ships[i] += weights[index]
            index+=1
      return index == len(weights)
ob = Solution()
print(ob.shipWithinDays([3,2,2,4,1,4],3))

入力

[3,2,2,4,1,4]
3

出力

6