Расчет результатов при нарезке стержней

Question

Я изучаю алгоритм резки стержней из книги CLRS.

Я верю, что понимаю логику, и мое решение ниже было принято на этом OJ.

#include <climits>
#include <iostream>

using namespace std;

int prices[101];
int result[101];

int function(int length)
{

    if (length == 0)
        return 0;    

    if (result[length] != INT_MIN)
    {
        return result[length];
    }

    //calculate result for length
    //if cutting the rod is more profitable, this variable will get overwritten in the loop below
    int current_max = prices[length];

    for (int cut_size = 1; cut_size < length; cut_size++)
    {
        int a;
        int b;
        a = function(cut_size);     //this question is about this step
        b = function(length - cut_size);
        if (a + b > current_max)
            current_max = a + b;
    }
    result[length] = current_max;
    return current_max;
}

int main() {

    int number_of_test_cases;
    int length_of_rod;

    cin>>number_of_test_cases;

    while (number_of_test_cases--)
    {
        cin>>length_of_rod;

        for (int i = 1; i <= length_of_rod; i++)
        {
            cin>>prices[i];
            result[i] = INT_MIN;
        }

        //profit of cutting rod to size 1
        result[1] = prices[1];

        cout<<function(length_of_rod)<<endl;
    }
    return 0;
}

Выше я реализовал логику, описанную в книге, за исключением небольшой модификации, о которой и рассказывается в этом посте.

Из книги

1: let r[0..n] be a new array
2: r[0] = 0
3: for j = 1 to n
4:    q = -1
5:    for i = 1 to j
6:       q = max(q, p[i] + r[j-i])
7:    r[j] = q
8: return r[n]

p - входной массив, содержащий прибыль для длины стержня от 1 до n, а r - для сохранения результатов.

Почему в строке 6 здесь r[i] не используется вместо p[i], когда r[i] уже содержит лучшую цену, по которой стержень длины i можно продать? Возможно, что r[i] содержит более высокое значение, чем p[i], подразумевая, что стержень длины i может получить более высокую цену после обрезки, а не быть проданным за штуку. Конечно, для последнего запуска цикла, когда i = j и стержень длины j не обрезается, это должно быть p[i], потому что r[j] - это значение, которое вычисляется, и оно не ' пока не существует. Но я запутался в других циклах цикла, когда пруток режется.

Мое решение использует логику q = max (q, r[i] + r [ji]) через эти утверждения -

a = function(cut_size);
b = function(length - cut_size);
if (a + b > current_max)
    current_max = a + b;

Если я изменю его с помощью = values ​​[cut_size] в соответствии с книгой, он все равно будет успешным в OJ.

Что мне здесь не хватает?

Answer 1

Рассматривать i быть длиной последнего отрезанного вами отрезка (всегда будет один, если вы не сделаете разрез, тогда весь стержень будет последним отрезком). Так как это один кусок, прибыль, которую вы получаете от этого p[i], Так что этот подход делает для всех возможных последних сокращений и использует тот, который максимизирует ценность.