Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

eins,Zweidimensionales Array

1、Zustandsübergangsgleichung：

• Legen Sie keine Gegenstände hinein : Abgeleitet von dp[i - 1][j], das heißt, die Rucksackkapazität ist j und der Maximalwert des Artikels i ist nicht darin platziert. Zu diesem Zeitpunkt ist dp[i][j] dp[i -. 1][j]. (Wenn das Gewicht des Gegenstands i größer ist als das Gewicht des Rucksacks j, kann der Gegenstand i nicht in den Rucksack gesteckt werden, sodass der Wert im Rucksack immer noch derselbe ist wie zuvor.)
• Platzieren Sie den Artikel i: Abgeleitet aus dp[i - 1][j - Gewicht[i]] ist dp[i - 1][j - Gewicht[i]] die maximale Kapazität des Rucksacks ohne Gegenstand i, wenn die Kapazität j - Gewicht[ i] Wert, dann ist dp[i - 1][j - Gewicht[i]] + Wert[i] (der Wert von Artikel i) der Maximalwert, den man erhält, wenn man Artikel i in den Rucksack legt

Also die rekursive Formel: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Gewicht[i]] + Wert[i]);

2. Initialisierung

(1) Ausgehend von der Definition von dp[i][j] muss der Gesamtwert des Rucksacks gleich sein, wenn die Rucksackkapazität j 0 ist, d. h. dp[i][0], unabhängig davon, welche Elemente ausgewählt werden 0.

(2) Zustandsübergangsgleichung dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Gewicht[i]] + Wert[i]); Wie man sieht, ist i von i-1 abgeleitet und muss daher initialisiert werden, wenn i 0 ist.

dp[0][j], das heißt: i ist 0, wenn die Artikelnummer 0 gespeichert wird, der maximale Wert, den ein Rucksack jeder Kapazität speichern kann.

Dann ist es offensichtlich, dass dp[0][j] 0 sein sollte, wenn j <Gewicht[0], da die Rucksackkapazität kleiner ist als das Gewicht des Artikels mit der Nummer 0.

Wenn j >= Gewicht[0], sollte dp[0][j] Wert[0] sein, da die Rucksackkapazität ausreicht, um die Artikelnummer 0 aufzunehmen.

for (int j = 0 ; j < weight[0]; j++) {
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

(3) Andere Indexinitialisierung:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Gewicht[i]] + Wert[i])

dp[1][1] = max(dp[0][1], dp[0][1- Gewicht[i]] + Wert[i]) muss links und darüber liegen,

Daher muss er initialisiert worden sein und kann auf einen beliebigen Wert gesetzt werden. Der Einfachheit halber ist er standardmäßig auf 0 initialisiert.

2. Eindimensional (rollendes Array)

1. Im eindimensionalen dp-Array bedeutet dp[j]: Ein Rucksack mit einer Kapazität von j kann Gegenstände mit einem Maximalwert von dp[j] tragen.

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

2. Initialisierung

(1) dp[0]=0, da der maximale Wert der von einem Rucksack mit einer Kapazität von 0 getragenen Gegenstände 0 ist.

(2) Angenommen, der Wert der Elemente ist größer als 0.Um nicht durch den Anfangswert überschrieben zu werden, also dpArray-InitialisierungWenn , sind sie zunächst alle 0

3. Durchlaufreihenfolge

In umgekehrter Reihenfolge verfahren

Erklärung 1: Der Wert am Ende der Liste muss durch Vergleich mit dem vorherigen Wert ermittelt werden, der durch Durchlaufen der vorherigen Ebene erhalten wurde.

Erklärung 2: Für jeden Rucksack gibt es nur einen 01-Rucksack. Ob diese Tasche platziert ist oder nicht, hängt vom Status der vorherigen Tasche ab Die rechte Seite ist ein ausstehender Status des aktuellen Beutels. Im Code ist die Zahl auf der linken Seite erforderlich, um das Array auf der rechten Seite zu bestimmen, sodass die Zahl auf der linken Seite nicht zerstört werden kann, bevor die Zahl auf der rechten Seite berechnet wurde.

Erklärung 3: Für zwei Dimensionen kommt das Ergebnis jeder neuen dp-Zahl, die ich habe, von oben nach links. Tatsächlich sollte es in einer Dimension so sein, aber in einer Dimension, wenn es immer noch von links nach rechts ist meine tatsächliche Linke Die Zahlen wurden aktualisiert ( Die linke Seite ist nicht mehr die „ursprüngliche“ linke Seite!Dies führt zu Doppelzählungen ), selbst wenn es sich bei der Spitze immer noch um die ursprüngliche Spitze handelt, ist die erhaltene Zahl falsch.Und wenn wir in der Rucksackschicht (innere Schicht) von rechts nach links wechseln, wird das Element auf der linken Seite immer verwendetAufgrund meiner vorherigen Operation wird es nicht mit neuen Werten überschrieben., damit der richtige Wert ermittelt werden kann.

3. Bewerbung

1. Gegeben sei ein nicht leeres Array, das nur positive ganze Zahlen enthält. Ist es möglich, dieses Array in zwei Teilmengen aufzuteilen, sodass die Summe der Elemente der beiden Teilmengen gleich ist?

Hinweis: Die Elemente in jedem Array werden 100 nicht überschreiten und die Größe des Arrays wird 200 nicht überschreiten

Beispiel 1:

• Eingabe: [1, 5, 11, 5]
• Ausgabe: wahr
• Erläuterung: Das Array kann in [1, 5, 5] und [11] unterteilt werden.

analysieren:

Der Artikel ist ich,

Das Gewicht ist nums[i], der Wert ist ebenfalls nums[i] und das Rucksackvolumen ist sum/2.

Ähnlich wie 01 Rucksack

Zustandsübergangsgleichung:

dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) {
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}
// 集合中的元素正好可以凑成总和target
if (dp[target] == target) return true;

2. Es gibt einen Steinhaufen und das Gewicht jedes Steins ist eine positive ganze Zahl.

Wählen Sie in jeder Runde zwei beliebige Steine ​​aus und zerschmettern Sie sie. Angenommen, die Gewichte der Steine ​​seien x bzw. y und x <= y. Dann sind die möglichen Ergebnisse der Zerkleinerung wie folgt:

Wenn x == y, dann werden beide Gesteine ​​vollständig zerkleinert;

Wenn x != y, dann wird der Stein mit dem Gewicht x vollständig zerbrechen und der Stein mit dem Gewicht y wird ein neues Gewicht von yx haben.

Am Ende bleibt höchstens noch ein Stein übrig. Gibt das kleinstmögliche Gewicht dieses Steins zurück. Wenn keine Steine ​​mehr vorhanden sind, geben Sie 0 zurück.

Beispiel:

• Eingabe: [2,7,4,1,8,1]
• Ausgabe: 1

analysieren:

Versuchen Sie, die Steine ​​in zwei gleich schwere Stapel aufzuteilen, sodass nach der Kollision der kleinste Stein übrig bleibt

Teilen Sie es dann in zwei Steinhaufen auf. Das Gesamtgewicht eines Steinhaufens beträgt dp[Ziel] und das Gesamtgewicht des anderen Steinhaufens beträgt sum - dp[Ziel].

Bei der Berechnung des Ziels ist Ziel = Summe / 2, da es abgerundet wird, also muss Summe – dp[Ziel] größer oder gleich dp[Ziel] sein.

Dann beträgt das Mindestgewicht des nach der Kollision verbleibenden Steins (Summe – dp[Ziel]) – dp[Ziel]

for (int i = 0; i < stones.length; i++) {
//采用倒序
    for (int j = target; j >= stones[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
    }
}
//结果
sum - 2 * dp[target];

zitiert nach:Zufällige Notizen codieren