Pythonでボードを正方形にカットするための最小コスト

長さp、幅qのボードがあるとします。このボードをp*qの正方形に分割して、分割のコストを可能な限り最小限に抑える必要があります。各エッジの切削コストが示されます。

したがって、入力がX_slice =[3,2,4,2,5]の場合、Y_slice =[5,2,3]

その場合、出力は65になります

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

• res：=0
• 水平：=1、垂直：=1
• i：=0、j：=0
• i
• X_slice [i]> Y_slice [j]の場合、
  • res：=res + X_slice[i]*垂直
  • 水平：=水平+1
  • i：=i + 1
• それ以外の場合、
  • res：=res + Y_slice[j]*水平
  • 垂直：=垂直+1
  • j：=j + 1

例

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

def minCost(X_slice, Y_slice, m, n):
   res = 0
   X_slice.sort(reverse = True)
   Y_slice.sort(reverse = True)
   horizontal = 1
   vertical = 1
   i = 0
   j = 0
   while i < m and j < n:
      if (X_slice[i] > Y_slice[j]):
         res += X_slice[i] * vertical
         horizontal += 1
         i += 1
      else:
         res += Y_slice[j] * horizontal
         vertical += 1
         j += 1
   total = 0
   while (i < m):
      total += X_slice[i]
      i += 1
   res += total * vertical
   total = 0
   while (j < n):
      total += Y_slice[j]
      j += 1
   res += total * horizontal
   return res
m = 6; n = 4
X_slice = [3,2,4,2,5]
Y_slice = [5,2,3]
print(minCost(X_slice, Y_slice, m-1, n-1))

入力

[3,2,4,2,5],[5,2,3]

出力

65