了解自下而上的杆切割实施

Question

在算法导论(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]为我们提供了第一件切割的最佳尺寸.

我的问题是关于外部循环迭代是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中的拼写错误还是我在这里遗漏了什么？

我的情况你们有些人不知道切杆问题是什么,这是一个例子.

Answer 1

这是关键: for i = 1 to j

i将开始在1和增加价值,但不得超过价值j.

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