寻找用 Python 绘制房屋的最低成本的程序

假设有一个大小为m的数组,代表一个小城市的m栋房子,每栋房子都必须涂上n种颜色中的一种(颜色从1到n标注),而且有些房子已经涂上了,所以不需要再画一次。有相同颜色的房屋称为邻里。我们有数组houses,其中houses[i]表示房子的颜色,如果颜色值为0,则表示房子还没有上色。我们有另一个称为成本的数组,这是一个二维数组,其中 cost[i, j] 表示用颜色 j+1 为房子 i 着色的成本。我们还有另一个名为 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]这样的,一共有三个邻域,[{2,2}, {1}, {2,2}]。粉刷第一个和最后一个房子的总成本 (10 + 1) = 11。

示例

让我们看下面的实现来更好地理解

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

以上是 寻找用 Python 绘制房屋的最低成本的程序 的全部内容, 来源链接: utcz.com/z/355853.html

回到顶部