切钢条问题

Rod-Cutting #

切钢条问题

钢条长度 i 和售价 P(i) 的对照表

Length i	1	2	3	4	5	6	7	8	9	10
Price P(i)	1	5	8	9	10	17	17	20	24	30
Cut ways	1	2	4	8

求给定长度 n 的钢条的最大销售额 R(n) ?

解：设长度为 n 的钢条的最大销售额为 R(n)

R(n) = Max {P(n), R(1) + R(n -1), R(2) + R(n - 2)}