动态规划 - 棒料问题 [英] Dynamic Programming - Rod Cutting Problem

问题描述

在算法导论（CLRS），Cormen等。说说解决棒切割的问题如下：（369页）

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

下面 P [I] 被切割杆的长度的价格我，研究[I] 是切杆的长度的收入我和 S [I] ，给我们的第一件切断最佳尺寸。

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.

我的问题是关于外部循环迭代Ĵ从1到n和内循环我认为是从1到n为好。

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.

在第6行我们比较Q（最大的收益获得了迄今为止）与研究[纪宝成]：中，previous切割过程中获得最大的收益。

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.

在 J = 1和I = 1 ，这似乎是罚款，但内循环的非常一次迭代，其中 J = 1 I = 2 ，也不会研究[纪宝成]：为r [1-2] = R [-1] ？我不知道，如果负折射率有道理这里。是，在CLRS一个错字或我失去了一些东西呢？

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.

感谢

推荐答案

这是关键：对于i = 1到j

我将开始在1和增加值的，但不得超过 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屋！