ロッド切断問題の簡単な解決策を実装しようとしています。以下は、単純な動的プログラミング ソリューションのコードです。
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
質問を削除しようとしましたが、既に回答があります。