PythonのCampusBikesII

キャンパスを表す2Dグリッドがあり、N人の労働者とM人の自転車があり、N <=Mの値であるとします。これで、各労働者と自転車はこのグリッド上で2D座標になります。したがって、各作業者と割り当てられた自転車との間のマンハッタン距離の合計が最小になるように、各作業者に1台の固有の自転車を割り当てたい場合。

2点p1とp2の間のマンハッタン距離は（p1、p2）=| p1.x--p2.x|であることがわかります。 + | p1.y--p2.y|。各作業員と割り当てられたバイクの間のマンハッタン距離の可能な最小合計を見つける必要があります。

したがって、入力がworkers =[[0,0]、[2,1]]の場合、bikes =[[1,2]、[3,3]]

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

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

• 関数helper（）を定義します。これにはa、b

  がかかります

  • 戻り値|a[0] -b [0] | + | a [1] --b [1] |

• 関数solve（）を定義します。これには、自転車、労働者、bikev、i：=0

  が必要です。

• info：=iとbikevのリスト

• 情報がメモにある場合は、

  • メモを返す[情報]

• 私が労働者のサイズと同じなら、

  • 0を返す

• temp：=無限大

• 0から自転車のサイズまでの範囲のjについては、次のようにします

  • ビーケフ[j]がゼロ以外の場合、

    • Bikev [j]：=1

    • temp：=tempの最小値、helper（workers [i]、bikes [j]）+solve（bikes、workers、bikev、i + 1）

    • Bikev [j]：=0

• memo [info]：=temp

• 温度を返す

• 関数assignBikes（）を定義します。これには労働者、自転車が必要です

• Bikev：=自転車のサイズと同じサイズのリスト、これをfalseで埋める

• memo：=新しい地図

• リターンソルブ（バイク、ワーカー、bikev）

例

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

class Solution(object):
   def helper(self,a,b):
      return abs( (a[0]-b[0]) ) + abs( (a[1] - b[1]) )
   def solve(self,bikes,workers,bikev,i=0):
      info = (i,tuple(bikev))
      if info in self.memo:
         return self.memo[info]
      if i == len(workers):
         return 0
      temp = float('inf')
      for j in range(len(bikes)):
         if not bikev[j]:
            bikev[j]=1
            temp = min(temp,self.helper(workers[i],bikes[j])+self.solve(bikes,workers,bi
kev,i+1))
            bikev[j]=0
      self.memo[info]= temp
      return temp
   def assignBikes(self, workers, bikes):
      bikev = [False for i in range(len(bikes))]
      self.memo={}
      return self.solve(bikes,workers,bikev)
ob = Solution()
print(ob.assignBikes([[0,0],[2,1]],[[1,2],[3,3]]))

入力

[[0,0],[2,1]] [[1,2],[3,3]]

出力

6