Rod Cutting Problem
長さが n の棒があります。ここで n = prices.length です。長さ k の切れ端は prices[k-1] で売れます。棒は好きなだけ整数の長さの切れ端に分割しても、そのまま1本で売ってもかまいません。すべて売って得られる金額の最大値を返してください。
関数
- pricesinteger-array
- prices[k-1] は長さ k の棒片の価格であり、棒材の長さは prices.length です
- 戻り値integer
- ロッド全体で稼げる最大金額
制約
1 ≤ prices.length ≤ 10001 ≤ prices[i] ≤ 105
例
- 入力
- prices = [2, 5, 7, 8]
- 出力
- 10
- 説明
- 長さ 2 のピースを 2 つ売ると、5 + 5 = 10 になります。ロッドをそのまま売ると 8 を得られ、長さ 1 のピースと長さ 3 のピースを売ると 2 + 7 = 9 になります。
- 入力
- prices = [1, 3, 8]
- 出力
- 8
- 説明
- 長さ3の棒全体は8で売れます。最適な切り方である長さ1と2に切る方法では、1 + 3 = 4しか得られないため、まったく切りません。
- 入力
- prices = [4, 6, 9, 11, 14]
- 出力
- 20
- 説明
- 長さ1の部材は、より長い部材よりも単位長さあたり4多く売れ、5本取れるため、棒を長さ1の部材5本に切ると20の収益になります。
発展問題
ロッドを最大m回まで切断できるとしたらどうでしょうか？その場合、表の各エントリは何を知っておく必要があるでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
棒を切る方法はどれも、左端に長さが1から
nまでの最初の部分があります。その部分を売った後、残りについて何を決める必要があるでしょうか？長さ
kの最初のピースを切り出すと、残りは長さn-kのロッドになります。その最適な売り方は、すでに切り出したピースには左右されません。したがって、より短い長さそれぞれについて最適な価格が必要で、その数はn+1個だけです。best[0..n]を短い方から長い方へ埋めていきます。best[0]は 0 で、best[len]は、1 からlenまでのすべてのkについてのprices[k-1] + best[len-k]の最大値です。k = lenを選ぶのは、ピースをそのまま売ることです。
解説
長さ n の棒は、2^(n-1) 通りに切ることができます。そのすべてを調べる必要はありません。最初のピースが何であっても、残りは同じ問いを抱えた、より短い棒です。したがって答えは長さごとに1つ、合計 n+1 個だけで、最も短いものから順に求めるのに必要なステップ数は O(n²) です。
最初のピースの長さをすべて試してみましょう
正しいが、最大のテストでは終わらない
考え方
どのような切り方でも、左端のピースの長さは1から棒の長さまでのいずれかのkで、その価格はprices[k-1]です。残りの部分は長さlength-kの棒を切り分ける計画になります。したがって、best(length)は長さが0の場合は0、それ以外の場合は、kをすべて試したときのprices[k-1] + best(length-k)の最大値です。ここでk = lengthなら、棒をそのまま売ります。どの計画にも最初のピースがあるため、この最大値ですべての計画を網羅できます。
各呼び出しは、より短い長さのすべてに分岐するため、長さが1単位増えるごとに呼び出し回数は倍増します。長さ40の棒では、およそ2^40、つまり10^12回の呼び出しになります。
アルゴリズム
best(length)を記述し、lengthが0の場合は0を返します。- 最初のピース
kを1からlengthまで試し、それぞれについてprices[k-1] + best(length-k)を計算します。 - それらの値のうち最大のものを返します。
best(n)を返します。
def cutRod(prices):
# The most money a rod of this length can earn
def best(length):
top = 0
for piece in range(1, length + 1):
# sell a first piece of this length, then cut the rest as well as possible
top = max(top, prices[piece - 1] + best(length - piece))
return top
return best(len(prices))長さごとの最安価格を、短い順に表示
考え方
再帰では同じ値が何度も計算されます。best(2)はbest(3)やbest(4)、さらに長いすべての棒から求められます。長さはn+1通りしかないので、それぞれを一度だけ計算して配列bestに格納します。ある長さの計算で参照するのはそれより短い長さだけなので、配列を0から順に埋めれば、値を参照するときには必ず計算済みです。
[2, 5, 7, 8]の場合、best[1]は2、best[2]は2 + 2と5の大きい方なので5、best[3]は7、best[4]は2 + 7、5 + 5、7 + 2、8のうち最大の値なので10です。
0/1ナップサックとは異なり、best[len-k]には長さkのピースがすでに含まれている場合があります。長さはいくらでも好きな回数だけ切れるため、これは望ましい動作です。長さlenでは、最初のピースとしてlen通りを試します。合計でn(n+1)/2ステップとなり、長さ1000の棒なら約5 × 10^5です。
アルゴリズム
- 要素がすべて 0 の
bestを、n + 1個の要素で作ります。 lengthを 1 から n まで変え、それぞれについて、最初のピースkを 1 からlengthまで試します。prices[k-1] + best[length-k]を計算し、最大の値をbest[length]に保持します。best[n]を返します。
def cutRod(prices):
n = len(prices)
# best[length]: the most money a rod of that length can earn
best = [0] * (n + 1)
for length in range(1, n + 1):
for piece in range(1, length + 1):
# a first piece of this length, then the best for what is left
earned = prices[piece - 1] + best[length - piece]
if earned > best[length]:
best[length] = earned
return best[n]
落とし穴と境界ケース
- 長さ
kに対してprices[k]を参照すること。これでは各ピースの長さを実際より 1 大きく見積もり、k = nで配列の範囲外にアクセスしてしまう。prices[k-1]を使うこと。 - 切らないピースにあたる
k = lengthを省くこと。その場合、best[1]は 0 のままとなり、[1, 3, 8]のスコアは 8 ではなく 3 になる。 - 単位あたりの価格が最も高い方法で貪欲に切ること。
[2, 7, 11, 13]では長さ 3 が単位あたりの価格で最も高いが、それを 11 で売って残りを 2 で売ると合計 13 になる一方、長さ 2 のピースを 2 つ作れば 14 になる。 - Python でトップダウンにメモ化すること。再帰の深さはロッドの長さと同じだけになる。長さ 1000 のロッドでは呼び出しが 1001 段になり、デフォルトの上限である 1000 を超える。配列をボトムアップで埋めること。
よくある質問4
ロッドカッティング問題の時間計算量は何ですか？
このテーブルは時間計算量が O(n²)、メモリ計算量が O(n) です。長さ len では最初のピースを len 通り試し、合計で n(n+1)/2 通り試します。答えを保存しない場合、長さ n のロッドに対する再帰呼び出しの回数はちょうど 2^n 回です。これは、それぞれの長さでそれより短いすべての長さを呼び出すためです。
なぜロッドカッティングは非有界ナップサック問題なのですか？
各ピースの長さ k を重さ k、価値 prices[k-1] のアイテムとして扱います。アイテムの個数に制限はなく、棒を容量 n のバッグと見なして、ちょうどいっぱいにします。すると、アイテムの合計価値の最大値が棒の最適な価格になります。
ロッドをどこで切るかは、どうやって見つけますか？
各長さについて、最良の価格を実現した最初のピース k を保存します。長さ n から始め、保存された長さのピースを切り取り、残った長さに移動して、0 になるまで繰り返します。これらのピースで最適な計画ができます。
すべてのカットに費用がかかる場合、解決策はどのように変わりますか？
棒を丸ごと売る場合は切断せず、それ以外の最初の切り分けではいずれも切断が1回発生します。したがって、best[len] は、prices[len-1] と、len 未満の k に対する prices[k-1] + best[len-k] - cost の最大値のうち、大きい方になります。テーブルの残りの部分はそのままです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def cutRod(prices):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
prices = [2, 5, 7, 8]
期待される出力
10