切割钢条-动态规划

时间:2022-12-03 12:59:27

切割钢条-动态规划

问题  C[J]  :以J为长度的钢条的最佳切割收益。

子结构:C[J]=MAX{P[J],C[J-I]+P[I]}

     一个钢条的最佳收益:假设至多一刀,要么切,要么不切,遍历所有情况,找出最大的收益情况

(P[J];不切,C[J-I]+P[I] : 在I位置切一刀)

初始化:C[0]=0;

追踪:rect[J],以J为长度的钢条,记录切割位置;

切割钢条-动态规划

(在网上找的图,N=N-记录的数字,算出右边的长度,为什么从右边?假如10要切成2和8

那么只会左边是2,右边是8,所以小的数字会在左边,大的在右边?(不知道对不对)

代码:

切割钢条-动态规划