LeetCode DayDynamic Programming Teil 3

0-1 Taschenproblem

Beschreibung des Themas

Ming ist ein Wissenschaftler, der an einer wichtigen internationalen wissenschaftlichen Konferenz teilnehmen muss, um seine neuesten Forschungsergebnisse vorzustellen. Er muss einige Forschungsmaterialien mitbringen, hat aber nur begrenzten Platz in seinem Koffer. Zu diesen Forschungsmaterialien gehören Versuchsgeräte, Literatur, Versuchsproben usw., die jeweils einen anderen Raum einnehmen und einen anderen Wert haben.

Mings Gepäckraum ist N. Fragen Sie Ming, wie er die Forschungsmaterialien mit dem größten Wert transportieren soll. Jedes Forschungsmaterial kann nur einmal ausgewählt werden, und es gibt nur zwei Möglichkeiten: wählen oder nicht wählen, und es kann kein Ausschneiden erfolgen.

Eingabebeschreibung
Die erste Zeile enthält zwei positive Ganzzahlen, die erste Ganzzahl M repräsentiert die Art der Forschungsmaterialien und die zweite positive Ganzzahl N repräsentiert Mings Gepäckraum.

Die zweite Zeile enthält M positive ganze Zahlen, die den von jeder Art von Forschungsmaterial eingenommenen Platz darstellen.

Die dritte Zeile enthält M positive ganze Zahlen, die den Wert jedes Forschungsmaterials darstellen.

Ausgabebeschreibung
Geben Sie eine Ganzzahl aus, die den maximalen Wert der Forschungsmaterialien darstellt, die Ming tragen kann.

Eingabebeispiel
6 1
2 2 3 1 5 2
2 3 1 5 4 3

Ausgabebeispiel
5

Hinweise
Ming kann 6 Forschungsmaterialien transportieren, aber der Gepäckraum beträgt nur 1, und das Forschungsmaterial, das 1 Platz einnimmt, ist 5 wert, daher ist die endgültige Antwort Ausgabe 5.

Datenbereich:
1 <= N <= 5000
1 <= M <= 5000
Der von den Forschungsmaterialien eingenommene Platz und der Wert der Forschungsmaterialien betragen jeweils weniger als oder gleich 1000.

public class Main{
    public static void main (String[] args) {
    /* code */
    Scanner s = new Scanner(System.in);

        int M = s.nextInt();
        int N = s.nextInt();
        // clear buffer symbol /n
        s.nextLine();

    String w = s.nextLine();
    String v = s.nextLine();

    int[] weight = Arrays.stream(w.split(" "))
                        .mapToInt(Integer::valueOf)
                        .toArray();
    int[] value = Arrays.stream(v.split(" "))
                        .mapToInt(Integer::valueOf)
                        .toArray();

    int[][] dp = new int[M][N+1];


    for(int i=weight[0]; i<=N; i++){
        dp[0][i] = value[0];
    }

    for(int i=1; i<M; i++){
        for(int j=1; j<=N; j++){
            if(weight[i] > j){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }

        }
    }

    System.out.println(dp[M-1][N]);
    }
}




</p>
<p>1, das dp-Array bedeutet, dass wir den Maximalwert für Artikel i und die Zieltaschengröße j erhalten können. Die Zeile gibt den Artikel an und die Spalte gibt die Größe der Tasche an.</p>

<p>2, für init initialisieren wir die 1. Zeile und die 1. Spalte (aber eigentlich initiieren wir die Spalte standardmäßig auf 0, das heißt)</p>

<p>3, die Regressionsrelation lautet: für jedes Element:<br>
    a: Wenn das Gewicht des Artikels schwerer ist als die Größe der Tasche, können wir den Artikel nicht auswählen und die aktuelle Größe entspricht der Größe der Sammlung der zuvor ausgewählten Artikel. <br>
    b: Wenn das Gewicht des Artikels in Ordnung ist, müssen wir die Größe der Sammlung der zuvor ausgewählten Artikel minus der Größe des aktuellen Artikels vergleichen (wenn wir das nicht tun, ist die Gesamtgröße die Größe + die Größe). des aktuellen Elements wird die Logik unseres dp-Arrays unterbrochen).</p>

<p>Hier ist die Reihenfolge der Doppelschleife, da wir ein 2D-Array verwenden können, um alle Ergebnisse aufzuzeichnen und in der vorherigen Zeile nach der aktuellen Zeile zu suchen.</p>
<h2>


  Wir können es auch mit einem 1D-Array realisieren.
</h2>



<pre class="brush:php;toolbar:false">    for(int i=1; i&lt;M; i++){
        for(int j=1; j&lt;=N; j++){
            if(weight[i] &gt; j){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }

ändern zu

int[] dp = new int[target+1];

for(int i=1; i<nums.length; i++){
    for(int j=target; j>=1; j--){
        if(nums[i] > j){
            continue;
        }
        dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
    }
}

---

416. Gleiche Teilmengensumme aufteilen

Geben Sie bei einem gegebenen ganzzahligen Array „nums“ „true“ zurück, wenn Sie das Array in zwei Teilmengen aufteilen können, sodass die Summe der Elemente in beiden Teilmengen gleich ist, andernfalls „false“.

Beispiel 1:

Eingabe: nums = [1,5,11,5]
Ausgabe: wahr
Erläuterung: Das Array kann als [1, 5, 5] und [11] partitioniert werden.
Beispiel 2:

Eingabe: nums = [1,2,3,5]
Ausgabe: false
Erläuterung: Das Array kann nicht in Teilmengen mit gleicher Summe aufgeteilt werden.

Einschränkungen:

1 <= nums.length <= 200
1 <= nums[i] <= 100
Originalseite

public boolean canPartition(int[] nums) {
    int sum = Arrays.stream(nums).sum();
    if(sum%2==1){
        return false;
    }
    int target = sum>>1;
    int[][] dp = new int[nums.length][target+1];

    for(int i=nums[0]; i<=target; i++){
        dp[0][i] = nums[0];
    }

    for(int i=1; i<nums.length; i++){
        for(int j=1; j<=target; j++){
            if(nums[i] > j){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i]);
            }
        }
    }

    return dp[nums.length-1][target] == target;
}








    <p></p><p>Das obige ist der detaillierte Inhalt vonLeetCode DayDynamic Programming Teil 3. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!</p>