一意の長さの値でカットされたロッドの最大合計価格を計算する

Question

ロッドカットの問題（n> 0、nは長さnの棒が​​あり、そのような整数の長さの部分にカットしたい総価格が最大になる）、pは価格のリスト、nは棒の長さです。私は棒を切って、最高の価格を得るために、その間に、長さがunqiueであることを保証する必要があります。つまり、すでに長さ= 3の長さをカットしていれば、長さ= 3

例えば、ベクトルp = {1,5,8,9,10,12,17,20}。私に最大の価格を与える：21と長さ：2,3,3。したがって、結果は20であり、長さは2,3,3の代わりに8,3

どのように私のコードを修正し、時間の複雑さを維持することができますかO（n^2）ありがとう。

int n = 8; 
vector<int> p = {1,5,8,9,10,12,17,20}; 

void cut_rod(vector<int>& p, int n){ 

    int r[n+1]; 
    int s[n+1]; 
    r[0] = 0; 

    for (int j = 1; j<=n; j++){ 
     int q = INT_MIN; 
     for (int i = 1; i <= j; i++){ 
      if(q < p[i-1] + r[j-i]){ 

       q = p[i-1] + r[j-i]; 
       s[j] = i; 
      } 
     } 
     r[j] = q; 
    } 
    return r[n]; 

} 

Answer 1

指定された長さのピースを保存するときは、n + 1のn + 1マトリックスを使用できます。このようにして、同じサイズのピースが一定の時間内にあるかどうかをチェックし、行をコピーすると線形時間がかかるので、複雑さは依然としてO（n^2）ですが、空間の複雑さはO（n^2）です。

以下のgeeksforgeeksでコードを変更しました。

// A Dynamic Programming solution for Rod cutting problem 
#include<stdio.h> 
#include<limits.h> 
using namespace std; 
// A utility function to get the maximum of two integers 
int max(int a, int b) { return (a > b)? a : b;} 

/* Returns the best obtainable price for a rod of length n and 
price[] as prices of different pieces */ 
int cutRod(int price[], int n) 
{ 
    int pieces[n+1][n+1];  
    int val[n+1]; 
    val[0] = 0; 
    int i, j; 

    // Build the table val[] in bottom up manner and return the last entry 
    // from the table 
    for (i = 1; i<=n; i++) 
    { 
     int max_val = INT_MIN, ind = -1; 
     for (j = 1; j <= i; j++) { 
      if (max_val < price[j - 1] + val[i-j]) { 
       if (pieces[i-j][j] != 1) {     
        max_val = price[j - 1] + val[i-j]; 
        ind = j; 
       } 
      } 
     } 
     val[i] = max_val; 
     for (int k = 0; k <= n; ++k) { // Copy the pieces 
      pieces[i][k] = pieces[i-ind][k]; 
     } 
     pieces[i][ind] = 1; // Add the piece of length ind (which is the max j) 
    } 
    return val[n]; 
} 

/* Driver program to test above functions */ 
int main() 
{ 
    int arr[] = {1,5,8,9,10,12,17,20}; 
    int size = sizeof(arr)/sizeof(arr[0]); 
    printf("Maximum Obtainable Value is %dn", cutRod(arr, size)); 
    getchar(); 
    return 0; 
} 

DPアルゴリズムは、アレイのValのi番目の位置に保存し、それを0からnまで進み、長さのロッドの最大価格I。長さiの棒のカットを0からnまで続く配列である小片[i]に保存します。位置jに1があれば、最大値val [i]を得ることを意味します長さjのここで、ある長さiについてのDPアルゴリズムは、長さjのカットを作成し、長さjの価格の価格と、既に計算された長さi-jの残りの部分の最大価格との合計を計算する。この合計はいくつかのjの最大値を持ちます。つまり、price [j-1] + val [i-j]がmax（ここでjは既存のカットではありません）になります。それで今、長さiについては、長さjの断片と長さi-jの断片が、断片[i-j]で保存しています。ここでピースを取得するにはピースピース[i - j]をコピーし、長さjのピースを追加する必要があります。あなたは1文字の変数名を使用しているのはなぜ

あなたはその

for (int i = 0; i <= n; ++i) 
    if (pieces[n][i] == 1) cout << i << ' ';