Расчет результата при резании стержня - PullRequest
Новая
       43

Расчет результата при резании стержня

0 голосов
/ 28 августа 2018

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

Мне кажется, я понимаю логику, и мое решение, принятое ниже, было принято this 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 [j-i]) через эти утверждения - 

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

Если я изменю его с = ценами [cut_size] в соответствии с книгой, он все еще успешен в OJ.

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

1 Ответ

0 голосов
/ 29 августа 2018

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

...