Python程序：查找切割木棍的最小成本

假设我们有一个值n和一个名为cuts的数组。考虑一根长度为n个单位的木棍。木棍从0到n标记。这里cuts[i]表示我们可以切割的位置。我们应该按顺序执行切割，但是我们可以根据需要更改切割的顺序。这里一次切割的成本是待切割木棍的大小，总成本是所有切割成本的总和。我们必须找到切割的最小总成本。

因此，如果输入类似于n = 7，cuts = [5,1,4,3]，则输出将为16，因为如果我们按[3,5,1,4]的顺序排列它们，则首先从长度为7的木棍上切割3，所以成本为7，然后我们有两部分长度为3和4，然后切割5，所以成本为4，到目前为止总成本为7+4=11，然后从木棍大小为2的地方切割4，所以总成本为7+4+2 = 13，最后切割3，所以成本为3，最终成本为7+4+2+3 = 16。

为了解决这个问题，我们将遵循以下步骤：

  • cuts := 一个列表，其中cuts中的元素按排序顺序排列，并在开头插入0并在结尾插入n

  • m := cuts的大小

  • cost := 创建一个大小为m x m的方阵并填充0

  • 对于k从2到m - 1，执行

    • 对于i从0到m - 1，执行

      • j := i + k

      • 如果j >= m，则

        • 进入下一次迭代

      • cost[i, j] = (cuts[j] - cuts[i]) + (cost[i, s] + cost[s, j] 在所有s在range(i+1, j-1)中的最小值)

    • 返回cost[0, m-1]

示例

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

def solve(n, cuts):
   cuts = [0] + sorted(cuts) + [n]
   m = len(cuts)
   cost = [[0]*m for _ in range(m)]

   for k in range(2, m):
      for i in range(m):
         j = i + k
         if j >= m:
            continue
         cost[i][j] = (cuts[j]-cuts[i]) + min(cost[i][s] + cost[s][j] for s in range(i+1, j))

   return cost[0][m-1]

n = 7
cuts = [5,1,4,3]
print(solve(n, cuts))

输入

7, [5,1,4,3]

输出

16

更新于：2021年10月6日

693 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告