-1

ロッド切断アルゴリズムを知っています。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

私の質問は、特定の長さのロッドを切断することの最大値 (価格) を見つけることができますが、その特定のロッドの切断の長さをどのように見つけることができますか?

4

1 に答える 1

2

関数を更新しcutRodて、ボトムアップ アプローチで上昇するときに、どこから最適な結果が得られたかを思い出そうとすることもできます。(つまり、そのステップに到達するために切断した最後のロッド) 上昇を終えたら、戻る前に、到達した最終ポイントから開始し、切断した各ロッドを長さ 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;
}
于 2016-03-19T04:05:45.037 に答える