ロッドカッティング - 動的計画

Question

問題文

---

ロッドカット問題は以下の通りです。長さがnインチのロッドとのテーブルがi = 1, 2, 3,....nの場合、棒を切断して販売することによって得ることができる最大収益Rnを決定します。長さがnの棒についての価格Pnが十分に大きい場合、最適解は全く切断を必要としないことに留意されたい。

n=4を考慮してください。図は、長さが4インチの棒を切り取るすべての方法を示しています。切り口を全く持たない方法を含みます。 4インチのロッドを2インチの2つの部分に切断すると、収入はP2+P2=5+5=10となり、最適です。

以下のコードは、ロッド切断のためのソリューションを構築するボトムアップアプローチです。

for (i = 1; i<=n; i++) 
{ 
    int q = INT_MIN; 
    for (j = 0; j < i; j++) 
     q= max(q, p[j] + r[i-j-1]); 
    r[i] = q; 
} 
return val[n]; 

なぜ補助配列r[n+1]が必要ですか？問題は、配列pだけを使用して解決することはできませんでしたか？ロッドの長さnと0を切断するとp [-1]にアクセスできないので使用されますか？ pが新しい値に更新されない場合、なぜq = max(q, p[j] + r[i-j-1])を使用していますか？

Answer 1

質問を正しく理解していれば、実装からrを削除することはできません。明らかにrのセマンティクスは

r[i] = maximum profit attainabble by cutting a rod of length i 
     into pieces of the lengths 1,...,n 

であり、それは内側のループにアクセスする必要があります。内側ループにおける再発関係はrの情報が評価のために必要であることを意味する

q = the more profitable choice between not cutting a rod of length j 
    and cutting a rod of length j (in which case we take p[j] as 
    profit plus the maximum attainable profit of cutting the remaining 
    rod, which has length j-i) 

に変換されます。

Answer 2

補助ループを内側ループに使用せずに半分だけ繰り返すことで、ロッドの切断に問題が発生します。

#include <stdio.h> 
#include <limits.h> 

int max(int a,int b) 
{ 
    return a>b?a:b; 
} 

int cut_rod(int p[],int n) 
{ 
    int q=0; 
    int r[n+1]; // Auxiliary array for copying p and appending 0 at index 0 
    int i,j; 

    if(n<0) 
     return 0; 
    else 
    { 
     r[0]=0; 
     for(i=0;i<n;i++) 
      r[i+1]=p[i]; 
     for(i=1;i<=n+1;i++) 
     { 
      q=INT_MIN; 
      for(j=0;j<=i/2;j++) 
       q=max(q,r[j]+r[i-j-1]); 
      r[i-1]=q; 
     } 
    } 
    return r[n]; 
} 

int main() 
{ 
    int p[]={1,5,8,9,10,17,17,20,24,30}; 
    int n=sizeof(p)/sizeof(int); 
    int val; 

    val=cut_rod(p,n); 
    printf("%d",val); 

    return 0; 
} 

Answer 3

その意味は完全に異なっているので、あなたには、二つの異なる配列rとpを使用する必要があります。値p[i]は、完全な（カットされていない）ボードの長さi+1がどれくらいかかるかを示します。値r[i]は、長さi+1のボードでどれくらいの利益を得ることができるかを示しています（完全またはカット）。これらの値は同じではありません。例えば、あなたの例ではp[3] = 9ですが、r[3] = 10のボードは、長さのボードを長さが2つの小さい方の小片に切断することができるので、2です。 2つの異なる意味を別々の配列に保つことは、常に最も良い考えです。 （メモリ制限が非常に厳しい場合を除いて）

また、実際には、ボードの長さは100ではないでしょう。しかし、このボードをカットして最適な利益を知りたい場合がありますそれ。配列が1つしかない場合は、配列を拡大する必要があります。言語の選択に応じて、2番目の配列を作成して1番目の配列をコピーすることもできます。したがって、単に2番目の配列を使用する方が簡単です。

（nが配列pのラングスよりも小さい場合）が可能であることに注意してください。 1つの配列のみを使用する単純なソリューションは、（1つのインデックスを使用して）次のようになります。

int p[]={0,1,5,8,9,10,17,17,20,24,30}; 
int n = 4; 
for (int i = 1; i <= n; i++) 
{ 
    for (int j = 1; j <= i/2; j++) 
     p[i] = max(p[i], p[j] + p[i - j]); 
} 
printf("%d\n", p[n]);