题目描述:
假如Serling公司出售一段长度为 i 英寸的钢条的价格为 pi( i =1,2,3,4…单位为美元)。钢条的长度为整英寸。假设Serling公司进了一批长度为n的钢条,那么怎么切割才能使利益最大呢? 如下为价格表:
输入描述:钢条长度n
输出描述:利益的最大值
在所有可能的两段切割方案中选择组合收益最大值,构成原问题的最优解。假设长度为n(n >= 1)的钢条的最大利润是Rn,我们可以用更短的钢条的最优切割收益来描述它:
Rn = max(Pn, R1 + Rn-1, R2 + Rn-2,…,Rn-1 + R1)。
采用动态规划,首先确定动态规划三要素:
最优子结构:max(Pn, R1 + Rn-1, R2 + Rn-2,…,Rn-1 + R1)
边界条件:i=1
状态转移公式: R1 + Rn-1
import java.util.Scanner;
/**
* @author Katakuly
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
int ans = getMax(p, n);
System.out.println(ans);
}
public static int getMax(int[] p, int n) {
int[] r = new int[n + 1];
for (int i = 1; i <= n; i++) {
int tmp = -1;
for (int j = 1; j <= i; j++) {
tmp = Math.max(tmp, p[j] + r[i - j]);
}
r[i] = tmp;
}
return r[n];
}
}