我正在尝试为杆切割问题实施简单的解决方案。下面是天真和动态编程解决方案的代码,
public static int rodCutNaive(int[] a, int n) {
if (n == 1) {
return a[0];
}
int q = 0;
for (int i = 1; i <= n; i++) {
int optimalCut = a[i - 1] + rodCutNaive(a, n - i);
if (q < optimalCut) {
q = optimalCut;
}
}
return q;
}
public static int rodCutDPBottomUp(int[] a, int n) {
if (n == 1) {
return a[0];
}
int[] s = new int[a.length];
s[0] = a[0];
for (int i = 2; i <= n; i++) {
s[i - 1] = a[i - 1];
for (int j = 1; j <= i - 1; j++) {
int optimalCut = a[j - 1] + s[i - j - 1];
if (s[i - 1] < optimalCut) {
s[i - 1] = optimalCut;
}
}
}
return s[n - 1];
}
我用下面的方法测试了,
public void testRodCutEfficiency() {
int[] a = { 1, 5, 8, 9, 10, 17, 17, 20, 22, 25, 26, 29, 34, 35, 39, 45,
46, 47, 50, 51 };
long t1 = System.nanoTime();
for (int i = 0; i < 1000; i++)
Rod.rodCutNaive(a, a.length);
long t2 = System.nanoTime();
for (int i = 0; i < 1000; i++)
Rod.rodCutDPBottomUp(a, a.length);
long t3 = System.nanoTime();
System.out.println("Problem size = " + a.length);
System.out.println("Naive = " + (t2 - t1));
System.out.println("DP = " + (t3 - t2));
}
输出:
Problem size = 20
Naive = 7989627046
DP = 7913165707
可能是编译器对天真的版本进行了某种尾递归优化,还是 JVM 可能会记住以前调用方法的解决方案?
哦,对不起,伙计们。这是复制粘贴错误。我两次都调用了相同的方法。现在我改变了它,新的输出是,
Problem size = 20
Naive = 7764056945
DP = 1324966
我试图删除这个问题,但它已经有了答案。