时间戳

首页 > 解决方案 > 棒材切割结果计算

algorithm - 棒材切割结果计算

问题描述

我正在学习 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;

如果我根据书用 a = prices[cut_size] 修改它，它仍然在 OJ 上成功。

我在这里想念什么？

标签： algorithmdynamic-programmingclrs

解决方案

考虑是你切割的最后i一块的长度（总会有一个，如果你不做任何切割，那么整个杆就是最后一块）。由于它是单件，因此您从中获得的利润是。所以这种方法正在做的是尝试所有可能的最后一次削减并使用一个最大化价值的方法。p[i]

推荐阅读