ロッドのカットアルゴリズムでロッドのカットの長さをすべて知る方法は？ （動的プログラミング）

Question

私はロッドの切断アルゴリズムを知っています。 C++インプリメンテーションは、以下である：

// A Dynamic Programming solution for Rod cutting problem 
#include<stdio.h> 
#include<limits.h> 

// 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 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; 
     for (j = 0; j < i; j++) 
     max_val = max(max_val, price[j] + val[i-j-1]); 
     val[i] = max_val; 
    } 

    return val[n]; 
} 

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

出力である：

Maximum Obtainable Value is 22 

私の質問は、私は、特定の長さのロッドを切断する最大値（価格）を見つけることができるですが、どうやっての長さを見つけることができますその特定の棒を切る？

Answer 1

あなたはボトムアップのアプローチで上に行く間にを覚えて、最適な結果を得たを覚えておくことができます。 （つまり、そのステップに達するためにカットした最後のロッド）あなたが戻ってくる前に、あなたが到着した最後のポイントから出発して、あなたが長さ0に到着するまであなたがカットした各ロッドをトレースすることができます。あなたのボトムアップアプローチの基盤。

以下のような粗い実装があります。

int numRodsUsed; 
int cutRod(int price[], int rods[], int n) 
{ 
    int val[n+1]; 
    int lastRod[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; 
     int best_rod_len = -1; 
     for (j = 0; j < i; j++) 
     { 
      if(max_val < price[j] + val[i-j-1]) 
      { 
       max_val = price[j] + val[i-j-1]; 
       best_rod_len = j; 
      } 
     } 
     val[i] = max_val; 
     lastRod[i] = best_rod_len + 1; 
    } 

    for (i = n, j = 0; i>0; i -= lastRod[i]) 
    { 
     rods[j++] = lastRod[i]; 
    } 
    numRodsUsed = j; 

    return val[n]; 
} 

int main() 
{ 
    int arr[] = {1, 5, 8, 9, 10, 17, 17, 20}; 
    int size = sizeof(arr)/sizeof(arr[0]); 
    int rods[size+1]; 
    int i; 
    printf("Maximum Obtainable Value is %d\n", cutRod(arr, rods, size)); 
    printf("Rod lengths are: %d", rods[0]); 
    for(i = 1; i < numRodsUsed; i++) 
    { 
     printf(" %d", rods[i]); 
    } 
    printf("\n"); 
    getchar(); 
    return 0; 
}