如何知道杆切割算法中杆的所有长度？ （动态编程）

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;
}