Pythonでスティックをカットするための最小コストを見つけるためのプログラム

値nとcutsという配列があるとします。長さn単位の木の棒があると考えてください。スティックには0からnまでのラベルが付いています。ここで、cuts [i]は、カットできる位置を表します。順番にカットする必要がありますが、カットの順番は自由に変更できます。ここで、1カットのコストはカットするスティックのサイズであり、合計コストはすべてのカットのコストの合計です。削減の最小総コストを見つける必要があります。

したがって、入力がn =7、cuts =[5,1,4,3]の場合、出力は16になります。これは、[3,5,1,4]のように注文すると、最初に長さ7から3なので、コストは7です。次に、長さ3と4の2つの部分があり、5でカットします。したがって、コストは4です。これまでの合計は、7 + 4 =11で、スティックサイズ2から4でカットします。 、したがって、合計コストは7 + 4 + 2 =13であり、最終的に3で削減されるため、コストは3になり、最終コストは7 + 4 + 2 + 3=16になります。

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

• cuts：=カット内の要素がソートされた順序であり、最初に0を挿入し、最後にnを挿入するリスト

• m：=カットのサイズ

• コスト：=サイズm x mの正方行列を作成し、0で埋めます

• 2からm-1の範囲のkの場合、実行

  • 0からm-1の範囲のiの場合、実行

    • j：=i + k

    • j> =mの場合、

      • 次のイテレーションに行く

    • cost [i、j] =（cuts [j] --cuts [i]）+最小値（cost [i、s] + cost [s、j] for all s in range（i + 1、j-1））

  • 返品費用[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