Pythonで家を塗装するための最小コストを見つけるためのプログラム

サイズmの配列があり、小都市のmの家を表すとします。各家は、n色のいずれかで塗装する必要があります（色は1からnまでのラベルが付けられています）。また、一部の家はすでに塗装されているため、もう一度ペイントします。同じ色で着色されている家は近所と呼ばれます。配列housesがあり、houses [i]は家の色を表し、色の値が0の場合、家はまだ色付けされていないことを表します。コストと呼ばれる別の配列があります。これは2D配列で、costs [i、j]は家iを色j+1で着色するためのコストを表します。また、targetと呼ばれる別の入力値もあります。残りのすべての家を、正確に目標数の近隣が存在するように塗装するために必要な最小コストを見つける必要があります。解決策が得られない場合は、-1を返します。

したがって、入力が家のようなものである場合=[0,2,1,2,0]コスト=[[1,10]、[10,1]、[10,1]、[1,10]、[5、 1]] n =2 target =3の場合、一部の家はすでにペイントされているため、出力は11になります。したがって、[2,2,1,2,2]のように家をペイントする必要があります。3つあります。近隣、[{2,2}、{1}、{2,2}]。そして、最初と最後の家をペイントするための総コスト（10 + 1）=11。

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

• m：=家のサイズ

• 関数helper（）を定義します。これにはi、p_col、grpが必要です

• iがmと同じ場合、

  • grpがターゲットと同じ場合は0を返し、それ以外の場合はinf

• Houses [i]が0と同じでない場合、

  • return helper（i + 1、houses [i]、grp +（p_colがhouses [i]と同じでない場合は1、それ以外の場合は0）

• 合計：=inf

• 1からnの範囲の列については、実行してください

  • total =合計の最小値および（cost [i、col --1] + helper（i + 1、col、grp +（p_colがcolと同じでない場合は1、それ以外の場合は0）））

• 合計を返す

• メインの方法から次のようにします

• ans：=helper（0、-1、0）

• ansがinfでない場合は、ansを返します。それ以外の場合は-1

例

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

def solve(houses, cost, n, target):
   m = len(houses)

   def helper(i, p_col, grp):
      if i == m:

         return 0 if grp == target else float('inf')

      if houses[i] != 0:
         return helper(i + 1, houses[i], grp + int(p_col != houses[i]))

      total = float('inf')
      for col in range(1, n + 1):
         total = min(total, cost[i][col - 1] + helper(i + 1, col, grp + int(p_col != col)))

      return total

   ans = helper(0, -1, 0)
   return ans if ans != float('inf') else -1

houses = [0,2,1,2,0]

cost = [[1,10],[10,1],[10,1],[1,10],[5,1]]

n = 2

target = 3

print(solve(houses, cost, n, target))

入力

[0,2,1,2,0], [[1,10],[10,1],[10,1],[1,10],[5,1]], 2, 3

出力

11