Pythonで家と最寄りのメールボックスの間の最小合計距離を見つけるプログラム

Housesという配列があり、別の値kがあるとします。ここで、houses [i]は、通りに沿ったi番目の家の場所を表します。通りにk個のメールボックスを割り当て、各家と最も近いメールボックスの間の最小合計距離を見つける必要があります。

したがって、入力がhouses =[6,7,9,16,22] k =2の場合、メールボックスを7と18に配置すると、各家からの最小合計距離は| 6になるため、出力は9になります。 -7 | + | 7-7 | + | 9-7 | + | 16- 18 | + | 22-18 | =1 + 0 + 2 + 2 + 4 =9

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

• リストハウスを並べ替える

• 関数util（）を定義します。これにはidx、n、kが必要です

• kが1と同じ場合、

  • コア：=家[（n + idx）/2の商]

  • [|houses[i]のすべての要素の合計を返す-コア| idxからnの範囲の各iに対して]）

• 結果：=無限大

• idxからnの範囲のiの場合、実行

  • n --i

    • ループから出てきます

  • 結果：=結果の最小値とutil（idx、i、1）+ util（i + 1、n、k --1）

• 結果を返す

• メインの方法から、次の手順を実行します。

• return util（0、家のサイズ-1、k）

例

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

def solve(houses, k):
   houses.sort()
   def util(idx, n, k):
      if k == 1:
         core = houses[(n + idx) // 2]
         return sum([abs(houses[i] - core) for i in range(idx, n + 1)])
      result = float('inf')
      for i in range(idx, n + 1):
         if n - i < k - 1:
            break
         result = min(result, util(idx, i, 1) + util(i+1, n, k - 1))
      return result
   return util(0, len(houses) - 1, k)

houses = [6,7,9,16,22]
k = 2
print(solve(houses, k))

入力

[6,7,9,16,22], 2

出力

9