Pythonで本棚の棚を埋める

一連の本があるとします。ここで、i番目の本には厚さの本[i][0]と高さの本[i][1]があります。これらの本を、全幅shelf_widthの本棚に順番に配置したい場合。この棚に置く本のいくつかを選択した場合（それらの厚さの合計が<=シェルフ幅になるように）、本棚の全高が最大高さだけ増加した本棚の別のレベルの棚を構築します。置くことができる本。配置する本がなくなるまで、このプロセスを繰り返します。上記のプロセスの各ステップで、配置する本の順序は、指定された一連の本と同じ順序であることに注意する必要があります。この方法で棚を配置した後、本棚全体が可能な最小の高さを見つける必要があります。したがって、入力が− [[1,1]、[2,3]、[2,3]、[1,1]、[1,1]、[1,1]、[1,2]]の場合、およびself_width =4、

3つの棚の高さの合計が1+3 + 2 =6であるため、出力は6になります。本番号2が最初の棚にある必要はないことに注意してください。

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

• 本と同じサイズの配列dpを1つ作成し、無限を使用してこれを埋めます
• dp [0]：=本[0,1]
• 1から本の長さまでの範囲のiの場合– 1
  • curr_height：=0
  • temp：=self_width
  • j：=i
  • j> =0およびtemp– books [j、0]> =0、do
    • curr_height：=本の最大数[j、1]、curr_height
    • dp [i]：=dp [i]の最小値、curr_height +（j – 1> =0の場合はdp[j-1]、それ以外の場合は0）
    • temp：=temp – books [j、0]
    • jを1つ減らします
• dpの最後の要素を返す

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

例

class Solution(object):
   def minHeightShelves(self, books, shelf_width):
      """
      :type books: List[List[int]]
      :type shelf_width: int
      :rtype: int
      """
      dp = [float('inf') for i in range(len(books))]
      dp[0] = books[0][1]
      for i in range(1,len(books)):
         current_height = 0
         temp = shelf_width
         j = i
         while j>=0 and temp-books[j][0]>=0:
            current_height = max(books[j][1],current_height)
            dp[i] = min(dp[i],current_height +( dp[j-1] if j-1 >=0 else 0))
            temp-=books[j][0]
            j-=1
         #print(dp)
      return dp[-1]

入力

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

出力

6