Coffee之自底向上切钢管问题求解

同样是《Introduction to Algorithm 3ed》(英文PDF版可在yanwen.blog/show/获取),在动态规划第一部分作者讨论了切钢管问题。该问题有很多解法,比如自顶向下带备忘自顶向下自底向上等。

下面用Coffee实现的为自底向上的方法,不带切分步骤,只显示最终结果。

算法伪码描述详见《Introduction to Algorithm 3ed》英文版366页。

以下是Coffee描述:

bottomUpCutRod.coffee

#!/usr/bin/env coffee

###
Implementation of algorithm BOTTOM-UP-CUT-ROD in book - Introduction to Algorithm

@author YanWen <i@yanwen.email>
@file bottom_up_cut_rod.coffee
@modified 2017-12-09
###

###
The bottom-up version of rod-cutting probelem

@param Array priceList
@param Integer length (the length of rode)
@return Integer (calculated price)
###
bottomUpCutRod = (priceList, rodLength) ->
  calculatedPrice = (Array +rodLength).fill 0              # NOTE rod length equal to 0 is meaningless

  # Cut and store
  for index1 in [1..rodLength] by 1
    tempPrice = -1
    for index2 in [1..index1] by 1
      tempPrice = Math.max tempPrice, priceList[index2] + calculatedPrice[index1 - index2]

    calculatedPrice[index1 + 1] = tempPrice

  calculatedPrice[rodLength]


# NOTE              The price table
# NOTE length 1, 2, 3, 4,  5,  6,  7,  8,  9, 10
PRICE_LIST = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30]

argvs = process.argv.splice(2)
rodLength = argvs[0]

process.exit -1 if not rodLength

# Test
maxRevenue = bottomUpCutRod PRICE_LIST, rodLength
console.log "The max revenue is #{maxRevenue} when the rod length equal to #{rodLength}"

简单测试结果(在此长度最长为10):

$ ./bottomUpCutRod.coffee 9
The max revenue is 25 when the rod length equal to 9

参考:

  1. Introduction to Algorithms(Third Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press)
  2. 维基百科 – 动态规划
  3. CSDN – 苦_咖啡 – 【算法导论】动态规划之“钢管切割”问题

作者: YanWen

Web 开发者

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s