Natürliche Zahlen als Summe von Quadraten durch dynamische Programmierung darstellen

Question

Das Problem besteht darin, die minimale Anzahl von Quadraten zu finden, die die Summe einer Zahl n ergeben.

Einige Beispiele:

min[ 1] = 1 (1²)
min[ 2] = 2 (1² + 1²)
min[ 4] = 1 (2²)
min[13] = 2 (3² + 2²)

Ich bin mir bewusst, dass Lagranges Vier-Quadrate-Theorem die besagt, dass jede natürliche Zahl als Summe von vier Quadraten dargestellt werden kann.

Ich versuche, dieses Problem mit DP zu lösen.

Ich habe mir folgendes ausgedacht (es ist nicht korrekt)

min[i] = 1 where i is a square number
min[i] = min(min[i - 1] + 1, 1 + min[i - prev]) where prev is a square number < i

Welches ist der richtige DV-Weg, um dieses Problem zu lösen?

Answer 1

Ich bin mir nicht sicher, ob DP der effizienteste Weg ist, dieses Problem zu lösen, aber Sie haben nach DP gefragt.

min[i] = min(min[i - 1] + 1, 1 + min[i - prev]), wobei prev eine Quadratzahl < i ist
Das ist nahe dran, ich würde die Bedingung als

min[i] = min(1 + min[i - prev]) for each square number 'prev <= i'

Beachten Sie, dass für jede i müssen Sie die verschiedenen möglichen Werte von prev .

Hier eine einfache Implementierung in Java.

Arrays.fill(min, Integer.MAX_VALUE);
min[0] = 0;
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j*j <= i; ++j) {
        min[i] = Math.min(min[i], min[i - j*j] + 1);
    }
}

Answer 2

Es scheint mir, dass Sie nahe dran sind...

Du nimmst min() von zwei Termen, von denen jeder ein min[i - p] + 1 , wobei p entweder 1 oder ein anderes Quadrat < i ist.

Um dies zu beheben, nehmen Sie einfach den Wert min() von min[i - p] + 1 über alle p (wobei p ein Quadrat < i ist).

Das wäre a richtigen Weg. Vielleicht gibt es einen schnelleren Weg.

Außerdem könnte es die Lesbarkeit verbessern, wenn Sie die min[] y min() andere Namen :-)

P.S. Der obige Ansatz erfordert, dass Sie sich min[] entweder ausdrücklich oder als Teil Ihres DV-Rahmens. Andernfalls wäre die Komplexität des Algorithmus aufgrund der Rekursion etwa O(sqrt(n)!) :-p , obwohl der durchschnittliche Fall viel besser sein könnte.

P.P.S. Siehe @Nikita's Antwort für eine schöne Implementierung. Ich würde die folgenden Optimierungen hinzufügen... (Ich bin nicht pingelig mit seiner Implementierung - er hat sie als eine einfache Implementierung präsentiert).

1. Prüfen Sie, ob n ein perfektes Quadrat ist, bevor Sie in die äußere Schleife einsteigen: Wenn ja, ist min[n] = 1 und wir sind fertig.
2. Prüfen Sie, ob i ein perfektes Quadrat ist, bevor Sie in die innere Schleife einsteigen: Wenn ja, ist min[i] = 1, und die innere Schleife wird übersprungen.
3. Brechen Sie die innere Schleife ab, wenn min[i] auf 2 gesetzt wurde, denn es wird nicht besser (wenn es mit einem Quadrat getan werden könnte, wären wir dank der vorherigen Optimierung nie in die innere Schleife gekommen).
4. Ich frage mich, ob die Abbruchbedingung in der inneren Schleife geändert werden kann, um die Anzahl der Iterationen zu verringern, z. B. j*j*2 <= i oder sogar j*j*4 <= i . Ich glaube schon, aber ich habe es noch nicht ganz begriffen.

5. Bei großen i wäre es schneller, vor der inneren Schleife einen Grenzwert für j zu berechnen und j direkt damit zu vergleichen, um die Schleife zu beenden, anstatt j bei jeder Iteration der inneren Schleife zu quadrieren. Z.B..

   float sqrti = Math.sqrt(i);
   for (int j = 1; j <= sqrti; ++j) {

   Andererseits braucht man j^2 sowieso für den Rekursionsschritt, also kann man es genauso gut verwenden, solange man es speichert.

Answer 3

Zur Abwechslung hier eine andere Antwort:

Definieren Sie minsq[i, j] als die minimale Anzahl von Quadraten aus {1^2, 2^2, ..., j^2}, die in der Summe i ergeben. Die Rekursion lautet dann:

minsq[i, j] = min(minsq[i - j*j, j] + 1, minsq[i, j - 1])

D.h., um minsq[i, j] zu berechnen, verwenden wir entweder j^2 oder nicht. Unsere Antwort für n lautet dann:

minsq[n, floor(sqrt(n))]

Diese Antwort ist vielleicht konzeptionell einfacher als die zuvor vorgestellte, aber kodemäßig ist sie schwieriger, da man mit den Basisfällen vorsichtig sein muss. Die Zeitkomplexität für beide Antworten ist asymptotisch gleich.

Answer 4

Ich präsentiere einen verallgemeinerten, sehr effizienten dynamischen Programmieralgorithmus, um die minimale Anzahl von positiven ganzen Zahlen einer bestimmten Potenz zu finden, um ein bestimmtes Ziel in JavaScript zu erreichen.

Um zum Beispiel 50000 mit ganzen Zahlen der 4. Potenz zu erreichen, würde das Ergebnis lauten [10,10,10,10,10] oder 18571 mit ganzen Zahlen der 7. Potenz zu erreichen, würde bedeuten [3,4] . Dieser Algorithmus würde sogar mit rationalen Potenzen funktionieren, um 222 mit ganzen Zahlen von 3 / ₅ th wäre die Macht [ 32, 32, 243, 243, 243, 3125 ]

function getMinimumCubes(tgt,p){
  var maxi = Math.floor(Math.fround(Math.pow(tgt,1/p))),
      hash = {0:[]},
       pow = 0,
         t = 0;
  for (var i = 1; i <= maxi; i++){
    pow = Math.fround(Math.pow(i,p));
    for (var j = 0; j <= tgt - pow; j++){
      t = j + pow;
      hash[t] = hash[t] ? hash[t].length <= hash[j].length ? hash[t]
                                                           : hash[j].concat(i)
                        : hash[j].concat(i);
    }
  }
  return hash[tgt];
}

var target = 729,
    result = [];
console.time("Done in");
result = getMinimumCubes(target,2);
console.timeEnd("Done in");
console.log("Minimum number of integers to square and add to reach", target, "is", result.length, "as", JSON.stringify(result));

console.time("Done in");
result = getMinimumCubes(target,6);
console.timeEnd("Done in");
console.log("Minimum number of integers to take 6th power and add to reach", target, "is", result.length, "as", JSON.stringify(result));

target = 500;
console.time("Done in");
result = getMinimumCubes(target,3);
console.timeEnd("Done in");
console.log("Minimum number of integers to cube and add to reach", target, "is", result.length, "as", JSON.stringify(result));

target = 2017;
console.time("Done in");
result = getMinimumCubes(target,4);
console.timeEnd("Done in");
console.log("Minimum number of integers to take 4th power and add to reach", target, "is", result.length, "as", JSON.stringify(result));

target = 99;
console.time("Done in");
result = getMinimumCubes(target,2/3);
console.timeEnd("Done in");
console.log("Minimum number of integers to take 2/3th power and add to reach", target, "are", result);