假设公司出售一段长度为i英寸的钢条的价格为Pi（i = 1, 2, ...单位：美元），下面给出了价格表样例：
长度i 1 2 3 4 5 6 7 8 9 10
价格Pi 1 5 8 9 10 17 17 20 24 30
切割钢条的问题是这样的：给定一段长度为n英寸的钢条和一个价格表Pi，求切割方案，使得销售收益Rn最大。
当然，如果长度为n英寸的钢条价格Pn足够大，最优解可能就是完全不需要切割。
对于上述价格表样例，我们可以观察所有最优收益值Ri及对应的最优解方案：
R1 = 1，切割方案1 = 1（无切割）
R2 = 5，切割方案2 = 2（无切割）
R3 = 8， 切割方案3 = 3（无切割）
R4 = 10， 切割方案4 = 2 + 2
R5 = 13， 切割方案5 = 2 + 3
R6 = 17， 切割方案6 = 6（无切割）
R7 = 18， 切割方案7 = 1 + 6或7 = 2 + 2 + 3
R8 = 22， 切割方案8 = 2 + 6
R9 = 25， 切割方案9 = 3 + 6
R10 = 30，切割方案10 = 10（无切割）
更一般地，对于Rn（n >= 1），我们可以用更短的钢条的最优切割收益来描述它：
Rn = max(Pn, R1 + Rn-1, R2 + Rn-2,...,Rn-1 + R1)
首先将钢条切割为长度为i和n - i两段，接着求解这两段的最优切割收益Ri和Rn - i
（每种方案的最优收益为两段的最优收益之和），由于无法预知哪种方案会获得最优收益，
我们必须考察所有可能的i，选取其中收益最大者。如果直接出售原钢条会获得最大收益，
我们当然可以选择不做任何切割。
分析到这里，假设现在出售8英寸的钢条，应该怎么切割呢？
代码如下：
package 动态规划;
/**
* 钢条不同长度价格不同，求如何切割钢条卖出最划算
* 用到动态规划
* @author wangdong20
*
*/
public class Steel {
/**
* 自底向上非递归方法解决钢条切割问题，
* 不仅保存最优收益值，还保存对应的切割方案
* @param p 不同长度钢条的价格
* @param n 钢条的总长度
*/
public static int[][] extendedBottomUpCutRod(int[] p, int n){
/*if(n == 0){
return new int[][]{
{0}, {0}};
}*/
int[][] s = new int[2][n + 1]; // s[0][2]保存2米长钢条的最佳收益，s[1][2]保存2米长钢条的切割方案
s[0][0] = 0;
for(int j = 1; j <= n; j++){
int q = -99999;
for(int i = 1; i <= j; i++){
if(q < p[i] + s[0][j - i]){
q = p[i] + s[0][j - i];
s[1][j] = i;
}
}
s[0][j] = q;
}
System.out.print("
最终受益: " + s[0][n]);
return s;
}
/**
* 根据算法打印出长度为n的钢条完整的最优切割方案
* @param p 不同长度钢条的价格
* @param n 钢条的总长度
*/
public static void printCutRodSolution(int[] p, int n){
int result[][] = extendedBottomUpCutRod(p, n);
System.out.print("
钢板切除方案: ");
while(n > 0){
System.out.print(result[1][n] + " ");
n = n - result[1][n];
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO 自动生成方法存根
// 钢条的价格price[0]表示0米长钢条的价格，price[5]代表5米长钢条的价格
int price[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
System.out.println("The price: ");
for(Integer i : price){
System.out.print(i + " ");
}
printCutRodSolution(price, 8);
}
}
运行结果如下：
The price:
0 1 5 8 9 10 17 17 20 24 30
最终受益: 22
钢板切除方案: 2 6