Предположим, у вас есть стержень длины n, и вы хотите разрезать стержень и продать куски таким образом, чтобы получить максимальную общую сумму денег. Кусок длины i стоит число пи.

как пример..

Например, если у вас есть стержень длины 4, есть восемь различных способов разрезать его, и лучшая стратегия — разрезать его на две части длины 2, что дает вам 10.

Итак наш главный вопрос или намерение: Сколько существует способов разрезать стержень длины n?

2 ^n−1 , потому что есть n − 1 место, где мы можем делать разрезы, и в каждом месте мы либо делаем разрез, либо не делаем разрез.

Простое решение этой проблемы состоит в том, чтобы сгенерировать все конфигурации различных частей и найти конфигурацию с самой высокой ценой. Сначала мы пытаемся отрезать кусок длины 1 и комбинировать его с оптимальным способом разрезания стержня длины n − 1. Затем мы пытаемся отрезать кусок длины 2 и комбинировать его с оптимальным способом разрезания стержня длина n − 2. Мы пробуем все возможные длины, а затем выбираем наилучшую.

Из Дерева видно, что для поиска решения выполняется несколько одинаковых вычислений. Это может быть оптимизировано с помощью DP.

Подход «снизу вверх»: здесь мы сначала вычисляем решения для стержней меньшего размера, зная, что позже они будут использоваться для вычисления решений для стержней большего размера. Можно избежать повторных вычислений одних и тех же подзадач, создав временный массив val[] снизу вверх.

Временная сложность, необходимая для этого алгоритма, составляет o (n * n).

КОД:

// Решение с помощью динамического программирования для задачи резки стержня
#include‹stdio.h›
#include‹limits.h›

// Вспомогательная функция для получения максимума из двух целых чисел
int max(int ​​a, int b) { return (a › b)? а : б;}

/* Возвращает наилучшую возможную цену на стержень длины n и
price[] как цены различных кусков */
int cutRod(int price[], int n)
{
целое значение[n+1];
знач[0] = 0;
инт i,j;

// Строим таблицу val[] снизу вверх и возвращаем последнюю запись
// из таблицы
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]);
значение[i] = максимальное_значение;
}

вернуть значение[n];
}

/* Программа-драйвер для проверки вышеуказанных функций */
int main()
{
int arr[] = {1, 5, 8, 9, 10, 17, 17, 20,24 ,30};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Максимальное значение: %dn", cutRod(arr, size));
получить символ();
вернуть 0;
}

ссылка: www.geeksforgeeks.com