利益を最大化するための切削棒のアルゴリズム

Question

私はダイナミックプログラミングを通じて標準のロッド切断問題を解決しようとしています。見つけhereとhereとして、再発の関係があるように思わ：

prices = [1..n] 
array[1..n] 

array[1] = prices[1] 

for i in (2..n) 
{ 
    array[i] = INT_MIN 
    for j in (1..i-1) 
    { 
     array[i] = max(array[i],prices[j]+array[i-j]) 
    } 
} 

そしてarray[n]は、私たちの答えですnの値を返します。私の質問は、それは我々が長8の最大値を見つけようとしていると想像

array[i] = max(array[i],array[j]+array[i-j]) 

すべきではない

array[i] = max(array[i],prices[j]+array[i-j]) 

ラインです。ここで、4については、長さ4の単一ユニットを切断することによって得られる値が、3および1の切断長さによって得られる値よりも小さくなる、すなわちn = 4の場合、prices[4]が最適ではないことがわかります。しかし結果の配列をボトムアップするので、array[4]が最適です。だからarray[4]+array[4]はprices[4]+array[4]と比べてn = 8の最大値になりませんか？私の結果の解決策は、次のようになります。

prices = [1..n] 
array[1..n] 

for i in (1..n) 
    array[i] = prices[i] //prices[i] is the minimum value we can obtain by cutting it fully 

for i in (2..n) 
{ 
    for j in (1..i-1) 
    { 
     array[i] = max(array[i],array[j]+array[i-j]) // find out all possible (j,i-j) pairs, and compare with array[i] 
    } 
} 

これが間違っている場合は、どこで誤りがあるのか​​を教えてください。

Answer 1

array[i] = max(array[i],prices[j]+array[i-j])私には右のように見えます。

このアルゴリズムでは、jは、最初のカットのロッドの長さを表します。まず、長さがiの棒で始まり、jを切り捨てます。次に、i - jのロッドをどれだけ得ることができるかを知る必要があります。これは、jの長さを切り捨てただけなので、i - jのままです。しかし、ロッドを全体として販売したり、ロッドをカットして価値を高めたりするという選択肢があるので、少なくともこの値はprice[i-j]と高いことがわかります。

例：私たちは、配列[]は既に1,2,3のための最適値が含ま仮定長さ4のロッドを有する その後、我々は：

は長さ1の部分を切断

、その後どのようにチェック多くの我々は3

は、長さ2の部分をカットオフ長さの棒のために取得することができ、その後、我々は2

は長さ3の一部を切断した長さの棒のため を得ることができますどのくらい確認し、その後、確認してください長さ1の棒のためにどれくらい得ることができるか

最大を選択します。

我々はarray[i] = max(array[i],array[j]+array[i-j])

array[k]を使用した場合、我々は小片にカット場合は長さkのロッドの最大値を含みます。したがって、これらの値は、price[k]を使用した場合と比べて予想外に高くなります。

また、現在の再帰ステップでは、カットを1つ作成し、残りの最大値をチェックするのではなく、両側の最大値をチェックします（大きなカットの値が理想）