了解自下而上的杆切割实现 [英] Understanding the bottom-up rod cut implementation

问题描述

在算法简介(CLRS) ，Cormen等.如下讨论解决切杆问题(第369页)

EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
    let r[0...n] and s[0....n] be new arrays
    r[0] = 0

    for j = 1 to n:
        q = -infinity   

        for i = 1 to j:
            if q < p[i] + r[j - i]:  // (6)
                q = p[i] + r[j - i]
                s[j] = i
        r[j] = q

    return r and s

这里p[i]是在长度i处切割棒的价格，r[i]是在长度i和s[i]处切割棒的收益，为我们提供了第一片切割的最佳尺寸. /p>

我的问题是关于将j从1循环到n的外循环，以及将内部循环i从1循环到n的内循环.

在第6行，我们将q(到目前为止获得的最大收入)与r[j - i](在上一次削减期间获得的最大收入)进行比较.

当j = 1 and i = 1时，这似乎很好，但是j = 1 and i = 2不会在r[j - i] be r[1 - 2] = r[-1]内循环的下一个迭代吗?

我不确定在这里负数指标是否有意义.是CLRS中的错字，还是我在这里遗漏了什么?

我认为有些人不知道裁纸问题是什么，这是一个示例.

解决方案

这是关键:for i = 1 to j

i将从1开始，并增加值直至但不超过 j的值.

i永远不会大于j，因此j-i永远不会小于零.

In Introduction to Algorithms(CLRS), Cormen et al. talk about solving the Rod-cutting problem as follows(page 369)

EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
    let r[0...n] and s[0....n] be new arrays
    r[0] = 0

    for j = 1 to n:
        q = -infinity   

        for i = 1 to j:
            if q < p[i] + r[j - i]:  // (6)
                q = p[i] + r[j - i]
                s[j] = i
        r[j] = q

    return r and s

Here p[i] is the price of cutting the rod at length i, r[i] is the revenue of cutting the rod at length i and s[i], gives us the optimal size for the first piece to cut off.

My question is about the outer loop that iterates j from 1 to n and the inner loop i that goes from 1 to n as well.

On line 6 we are comparing q (the maximum revenue gained so far) with r[j - i], the maximum revenue gained during the previous cut.

When j = 1 and i = 1, it seems to be fine, but the very next iteration of the inner loop where j = 1 and i = 2, won't r[j - i] be r[1 - 2] = r[-1]?

I am not sure if the negative index makes sense here. Is that a typo in CLRS or I am missing something here?

I case some of you don't know what the rod-cutting problem is, here's an example.

解决方案

Here's the key: for i = 1 to j

i will begin at 1 and increase in value up to but not exceeding the value of j.

i will never be greater than j, thus j-i will never be less than zero.

这篇关于了解自下而上的杆切割实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！