如何知道棒切割算法中棒的所有切割长度？ （动态规划）

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

您可以更新函数 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;
}