как узнать всю длину срезов стержня в алгоритме нарезания стержня? (динамическое программирование)
Я знаю алгоритм резки стержня. Реализация с ++ ниже:
// 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
Мой вопрос в том, могу ли я найти максимальное значение (цену) обрезки стержня определенной длины, но как я могу найти длину надрезов в этом конкретном стержне?
Решение
Вы можете обновить функцию 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;
}
Другие решения
Других решений пока нет …