算法设计与分析基础 第八章谜题

习题8.1

6.切割木棍问题 为下列问题设计一个动态规划算法。已知小木棍的销售价格pi和长度i相关，i=1,2，…，n，如何把长度为n的木棍切割为若干根长度为整数的小木棍，使得所获得的总销售价格最大？该算法的时间效率和空间效率各是多少？

解答：令长度为n的木棍能获得的最大价格为profit[n]，递推公式为：profit[n] = max(pi[i] + profit[length - seg[i]]), 其中i = 1,2,3,...n；边界条件profit[0]=0。