Artikelübersicht

Dies ist eine Reihe von Artikeln, die ich in meiner Studie und meinem Memo zusammengestellt habe. Die vierte. Dies ist eine Fortsetzung dieses Artikels. Einführung in Algorithmen mit Java-Suche (Width Priority Search) In diesem Artikel

--bit vollständige Suche

Ich werde darüber lernen. Ich bin sicher, Sie werden die Erklärung der Berechnung sehen, also kommen Sie bitte.

Bit vollständige Suche

Früher dachte ich, dass dies eine binäre Suche war, aber es scheint anders zu sein. Lassen Sie uns herausfinden, um welche Art von Suche es sich handelt.

Ich habe es nachgeschlagen. Es scheint der Weg zu sein, alle Muster zu durchsuchen, wenn (wahrscheinlich) zwei Auswahlmöglichkeiten für jedes in einem Satz vorhanden sind. Ist es schwer zu verstehen? Ich werde sofort ein Beispiel vorstellen.

Beispiel: AtCoder --abc167-c "Skill Up"

Klicken Sie hier, um Problemsätze und Eingabebeispiele anzuzeigen.
* Bitte beziehen Sie sich so weit wie möglich auf den Problemlink

(Abschnittsstart) 【Problemstellung】 Takahashi, der mit der wettbewerbsfähigen Programmierung begonnen hat, hat M Algorithmen, die er lernen möchte. Anfänglich ist das Verständnis jedes Algorithmus 0. Als Takahashi in die Buchhandlung ging, wurden N Nachschlagewerke zum Verkauf angeboten. Das i-te Nachschlagewerk (1 ≤ i ≤ N) wird im Ci-Kreis verkauft, und durch Kauf und Lesen wird das Verständnis des j-ten Algorithmus für jedes j (1 ≤ j ≤ M) durch Ai, j verbessert. Ich werde. Sie können Ihr Verständnis auch nicht auf andere Weise verbessern. Takahashis Ziel ist es, das Verständnis aller M-Algorithmen auf X oder höher zu verbessern. Bestimmen Sie, ob Takahashi das Ziel erreichen kann, und berechnen Sie nach Möglichkeit den Mindestbetrag, der zum Erreichen des Ziels erforderlich ist.

[Beschränkungen] Alle Eingaben sind ganze Zahlen 1≤N,M≤12 1≤X≤10^5 1≤Ci≤10^5 0≤Ai,j≤10^5

【Eingang】 Die Eingabe erfolgt über die Standardeingabe im folgenden Format.

N M X
C1 A1,1 A1,2 ⋯ A1,M
C2 A2,1 A2,2 ⋯ A2,M
⋮
CN AN,1 AN,2 ⋯ AN,M

【Ausgabe】 Geben Sie -1 aus, wenn Takahashi das Ziel nicht erreichen kann, andernfalls geben Sie den Mindestbetrag aus, der zum Erreichen des Ziels erforderlich ist.

(Ende des Abschnitts)

Wie bei diesem Problem ist der Ort, an dem das i-te Buch ** "kaufen / nicht kaufen" ** ist, wie das Problem der vollständigen Suche. Es gibt N Nachschlagewerke, und jedes Buch hat zwei Möglichkeiten: "Kaufen / Nicht Kaufen". Daher muss 2 ^ N Mal gesucht werden. ↓

1. Buch	2. Buch	3. Buch	4. Buch	・・・	N-tes Buch
Kaufen or Nicht kaufen	Kaufen or Nicht kaufen	Kaufen or Nicht kaufen	Kaufen or Nicht kaufen	Kaufen or Nicht kaufen	Kaufen or Nicht kaufen

Korrekt. Für jedes der N Bücher gibt es zwei Möglichkeiten, also gibt es zwei Möglichkeiten. Wenn hier buy = 1 und nicht buy = 0 ist, kann dies in binären Ticks ausgedrückt werden.

Angenommen, das erste Volumen ist N, N-1, N-2, ..., 3,2,1 von der oberen Ziffer, wenn beispielsweise N = 5, "01001" bedeutet, das 4. und 1. Buch zu kaufen.

Übrigens kann mathematisch gesehen gesagt werden, dass "die Anzahl der Teilmengen von N Nachschlagewerken, die gekauft werden sollten". Wenn die Menge von N Nachschlagewerken beispielsweise {1,2,3, ..., N-1, N} ist, kann die Teilmenge beim Kauf des ersten und dritten Buches als {1,3} ausgedrückt werden. Richtig. Diese "Anzahl von Teilmengen" kann auch als 2 ^ N ausgedrückt werden. Sie können die beiden Optionen "Zur Teilmenge hinzufügen oder nicht hinzufügen" auf jedes Nachschlagewerk anwenden (das Nachschlagewerk wird zu diesem Zeitpunkt mathematisch als Original oder Element bezeichnet).

Die Teilmenge, ob 3 Bücher gekauft werden sollen, lautet beispielsweise wie folgt.

{000}Buy ・ ・ Ich kaufe kein einziges Buch
{001}・ ・ ・ Kaufen Sie nur das erste Buch
{010}・ ・ ・ Kaufen Sie nur das zweite Buch
{011}・ ・ ・ Kaufen Sie das erste und zweite Buch
{100}・ ・ ・ Kaufen Sie nur das dritte Buch
{101}・ ・ ・ Kaufen Sie das 1. und 3. Buch
{110}・ ・ ・ Kaufen Sie das 2. und 3. Buch
{111}・ ・ ・ Kaufen Sie alle 3 Bücher

Sie können sehen, dass es genau 2 ^ 3 = 8 Möglichkeiten gibt.

Schauen wir uns eine Beispielantwort von Java an.

[Antwortbeispiel]

`main.java`


import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

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

		//Anzahl der Nachschlagewerke
		int n = sc.nextInt();

		//Anzahl der Algorithmen, die Sie lernen möchten
		int m = sc.nextInt();

		//Verständnis des Akquisitionsziels
		int x = sc.nextInt();

		//Preis des n-ten Nachschlagewerks
		int[] costs = new int[n];

		//Verbessertes Verständnis des m-ten Algorithmus im n-ten Nachschlagewerk
		int[][] a = new int[n][m];

		//Eingaben empfangen
		for (int i = 0; i < n; i++) {
			costs[i] = sc.nextInt();
			for (int j = 0; j < m; j++) {
				a[i][j] = sc.nextInt();
			}
		}

		//Verständnis des Niveaus des m-ten Algorithmus, der tmp-Variablen der Referenzbuchkosten, der Variablen zum Speichern der Referenzbuchkosten für jede Schleife, der Variablen, ob eine Algorithmuserfassung erreicht wurde
		int[] aTmp = new int[m];
		int costTmp = 0;
		List<Integer> costsSave = new ArrayList<>();
		boolean mastered = true;

		/*
		 *Etwas vollständige Suche von hier
		 */
		for (int i = 0; i < 1 << n; i++) {
			//Alle Schleifen der Bit-Vollsuche

			for (int j = 0; j < n; j++) {
				//Bestimmen, welches Nachschlagewerk für jede Schleife gekauft werden soll(Ob man das j-te Buch kauft)

				if ((1 & i >> j) == 1) {
					//Ich wurde hier erwischt=Zum Kauf hinzufügen(jth Buchkauf)

					for (int h = 0; h < m; h++) {
						//Verbessertes Verständnis des m-ten Algorithmus beim Kauf des j-ten Nachschlagewerks
						aTmp[h] += a[j][h];
					}

					//Preis des j-ten Buches
					costTmp += costs[j];
				}
			}

			//Nachdem ich das Nachschlagewerk gekauft habe, werde ich beurteilen, ob ich mich an den Algorithmus erinnern und den Preis behalten kann
			for (int h = 0; h < m; h++) {
				if (aTmp[h] < x) {
					//Wenn Sie sich nicht einmal an einen Algorithmus erinnern, NG
					mastered = false;
					break;
				}
			}

			if (mastered) {
				//Speichern Sie den Gesamtpreis vorübergehend
				costsSave.add(costTmp);
			}

			//Aufräumen
			for (int h = 0; h < m; h++) {
				aTmp[h] = 0;
			}
			costTmp = 0;
			mastered = true;
		}

		//Geben Sie den kleinsten Wert in der Liste aus. Wenn die Liste null ist"-1"Ausgabe
		int ans = Integer.MAX_VALUE;
		if (costsSave.isEmpty()) {
			ans = -1;
		} else {
			for (int cost : costsSave) {
				if (ans > cost) {
					ans = cost;
				}
			}
		}

		System.out.println(ans);

	}
}

Es ist so. Irgendwie verwende ich, wenn ich normalerweise Java schreibe, ungefähr zweimal unbekannte Symbole. "Suche alle Bits von hier" for (int i = 0; i < 1 << n; i++) Wann, "Ich wurde hier erwischt = zum Kaufziel hinzugefügt (j. Buchkauf)" if ((1 & i >> j) == 1) nicht wahr.

"&" "<<" ">>" werden "Bitoperatoren" genannt. Für eine detaillierte Verarbeitung gg und erläutern Sie bitte kurz. "&" Ist ein logisches Produkt, und "<<" und ">>" dienen zum Verschieben der Bitfolge nach rechts oder links.

(Beispiel) 01001 & 11000 = 01000 01001 << 1 = 10010 00100 >> 1 = 00010

Haben Sie die Verschiebung nach rechts oder links gesehen, die das logische Produkt für jedes Bit nimmt? Ich werde hier leichtfertig gehen.

Lassen Sie uns den Code erklären. Als allererstes for (int i = 0; i < 1 << n; i++) es ist hier. Beachten Sie den Teil der Wiederholungsbedingung für die Anweisung "i <1 << n". Zunächst ist das erste Symbol "<" (das rechts von i) eine Ungleichung und scheint korrekt zu sein. Das "<<" in "1 << n" ist also der Bitoperator (genau genommen der Verschiebungsoperator). Es bedeutet "1 << n", aber es bedeutet ** "n-mal 1 nach links verschieben" **. Wenn Sie beispielsweise 1 einmal nach links verschieben, ist dies "10" (ausgedrückt in binär, was 2 in dezimal ist).

Ähnlich Wenn Sie 1 zweimal nach links verschieben, ist dies "100" (ausgedrückt in binärer Notation. Es ist 4 (= 2 ^ 2) in Dezimalschreibweise). Dreimaliges Verschieben von 1 nach links ergibt "1000" (ausgedrückt in Binärform, 8 (= 2 ^ 3) in Dezimalzahl). Wenn Sie viermal 1 nach links verschieben, erhalten Sie "10000" (in Binärform, 16 (= 2 ^ 4) in Dezimalzahl).

Bild スクリーンショット 2020-05-21 21.06.48.png

Erstens wollte ich, was die Anzahl der Suchanfragen dieses Mal betrifft, über 2 ^ N Möglichkeiten nachdenken, da dies dem Kauf oder Nichtkauf für n Nachschlagewerke entspricht. Mit anderen Worten, wenn Sie dies für eine Anweisung umschreiben, for (int i = 0; i < Math.pow(2,n); i++) Kann auch umgeschrieben werden. Hast du irgendwie verstanden?

Lass uns als nächstes gehen.

if ((1 & i >> j) == 1) Es war schwer zu verstehen, nicht wahr? .. Wenn Sie die Klammern der if-Anweisung ins Japanische übersetzen, ist dies "ob das logische Produkt von ** 1 und i >> j gleich 1 ** ist".

Nehmen wir zum Beispiel i = 5 und j = 2 an. (Apropos Problem, wir sind dabei, die 5. Suche und den Kauf des 3. Buches in Betracht zu ziehen.) Wenn Sie 5 in eine Binärzahl konvertieren, ist dies 0101, und wenn Sie es zweimal nach rechts verschieben, sieht es wie folgt aus. スクリーンショット 2020-05-21 21.25.51.png

Nehmen Sie also das logische Produkt von diesem und 1 (0001). Wissen Sie, dass die Verwendung des logischen Produkts 1 ** bestimmt, ob die letzte Ziffer 1 ist oder nicht **? Zweimal verschieben und die letzte Ziffer ist 1, mit anderen Worten, zwei links von der letzten Ziffer suchen, um zu sehen, ob es 1 ist. Mit anderen Worten wird beurteilt, ob die j-te Ziffer von unten 1 ist. Wenn es 1 ist, ist es das Ziel des Kaufs.

Durchsuchen Sie alle Muster mit der for-Anweisung in "Alle Bits von hier aus suchen". Im Folgenden für den Satz "Bestimmen, welches Nachschlagewerk für jede Schleife gekauft werden soll (ob das j-te Buch gekauft werden soll)" wird das zu kaufende Buch durch dieses Muster spezifiziert.

Ist es ein bisschen schwierig? Folgen wir dem Prozess, indem wir ein konkretes Eingabebeispiel als Test verwenden.

【Eingabebeispiel】

n = 3 , m = 3 , x = 10 0. Buchkosten, Verständnis des Algorithmus 0,1,2 Kosten des ersten Buches, Verständnis des Algorithmus 0,1,2 Kosten des zweiten Buches, Verständnis des Algorithmus 0,1,2 Es war die Reihenfolge von. Es ist leicht zu verstehen und zählt ab 0 Start.

Dann suchen wir alle Bits. Da n = 3, Die Schleife von "Bit Full Search von hier" for(int i = 0 ; i < 1 << 3 ; i++) 1 << 3 verschiebt 0001 dreimal nach links, sodass es 1000 wird. Das ist acht. Es ist genau 2 ^ 3.

Schauen wir uns nacheinander i = 0 bis i = 7 an. Ich werde es entsprechend in eine Binärzahl umwandeln. Die Ziffer, die Sie mit j betrachten, ist fett dargestellt.

Wenn i = 0 (000) Wenn j = 0 (i = 00 0) Kaufen Sie das 0. Buch nicht, da es nicht "if ((1 & 000 >> 0) == 1)" ist Wenn j = 1 (i = 0 0) Kaufen Sie nicht das erste Buch, weil es nicht "if ((1 & 000 >> 1) == 1)" ist Wenn j = 2 (i = 0) Kaufen Sie das zweite Buch nicht, weil es nicht "if ((1 & 000 >> 2) == 1)" ist Wenn i = 1 (001) Wenn j = 0 (i = 001) Da es "if ((1 & 001 >> 0) == 1)" ist, kaufen Sie das 0. Buch Wenn j = 1 (i = 0 0 1) Kaufen Sie nicht das erste Buch, weil es nicht "if ((1 & 001 >> 1) == 1)" ist Wenn j = 2 (i = 0 01) Kaufen Sie das zweite Buch nicht, weil es nicht "if ((1 & 001 >> 2) == 1)" ist Wenn i = 2 (010) Wenn j = 0 (i = 01 0) Kaufen Sie das 0. Buch nicht, da es nicht "if ((1 & 010 >> 0) == 1)" ist Wenn j = 1 (i = 0 1 0) Kaufen Sie das erste Buch, da es "if ((1 & 010 >> 1) == 1)" ist Wenn j = 2 (i = 0 10) Kaufen Sie das zweite Buch nicht, weil es nicht "if ((1 & 010 >> 2) == 1)" ist Wenn i = 3 (011) Wenn j = 0 (i = 011) Da es "if ((1 & 011 >> 0) == 1)" ist, kaufen Sie das 0. Buch Wenn j = 1 (i = 0 1 1) Kaufen Sie das erste Buch, da es "if ((1 & 011 >> 1) == 1)" ist Wenn j = 2 (i = 0 11) Kaufen Sie das zweite Buch nicht, weil es nicht "if ((1 & 011 >> 2) == 1)" ist Wenn i = 4 (100) Wenn j = 0 (i = 10 0) Kaufen Sie das 0. Buch nicht, da es nicht "if ((1 & 100 >> 0) == 1)" ist Wenn j = 1 (i = 1 0) Kaufen Sie nicht das erste Buch, weil es nicht "if ((1 & 100 >> 1) == 1)" ist Wenn j = 2 (i = 1 00) Da es "if ((1 & 100 >> 2) == 1)" ist, kaufen Sie das zweite Buch Wenn i = 5 (101) Wenn j = 0 (i = 101) Da es "if ((1 & 101 >> 0) == 1)" ist, kaufen Sie das 0. Buch Wenn j = 1 (i = 1 0 1) Kaufen Sie nicht das erste Buch, weil es nicht "if ((1 & 101 >> 1) == 1)" ist Wenn j = 2 (i = 1 01) Da es "if ((1 & 101 >> 2) == 1)" ist, kaufen Sie das zweite Buch Wenn i = 6 (110) Wenn j = 0 (i = 11 0) Kaufen Sie das 0. Buch nicht, da es nicht "if ((1 & 110 >> 0) == 1)" ist Wenn j = 1 (i = 1 1 0) Kaufen Sie das erste Buch, da es "if ((1 & 110 >> 1) == 1)" ist Wenn j = 2 (i = 1 10) Kaufen Sie das zweite Buch, da es "if ((1 & 110 >> 2) == 1)" ist Wenn i = 7 (111) Wenn j = 0 (i = 111) Da es "if ((1 & 111 >> 0) == 1)" ist, kaufen Sie das 0. Buch Wenn j = 1 (i = 1 1) Da es "if ((1 & 111 >> 1) == 1)" ist, kaufen Sie das erste Buch Wenn j = 2 (i = 111) Da es "if ((1 & 111 >> 2) == 1)" ist, kaufen Sie das zweite Buch

Was denken Sie? Sie können nur die Ziffern kaufen, die genau 1 sind. Sobald Sie wissen, welches Nachschlagewerk Sie kaufen müssen, müssen Sie es nur noch berechnen. Ich überspringe diesen Vorgang.

Während ich schreibe, scheint es, dass ich es nicht implementieren kann, wenn mir gesagt wird, dass ich es implementieren soll, also ist der Rest Übung. Ich werde die folgenden Probleme von AtCoder lösen und später üben. ** Alles was du brauchst ist üben! !! !! ** ** ** AtCoder - abc079-c「Train Ticket」 AtCoder - abc128-c「Switches」

Dies ist das Ende des Explorationsabschnitts. Wie wäre es mit dem Studium der vollständigen Suche, der dichotomen Suche, der Suche mit Tiefenpriorität, der Suche mit Breitenpriorität und der vollständigen Suche mit Bit? Wenn Sie interessiert sind, folgen Sie bitte dem Link. Es ist eine kleine Übungszeit, also hoffe ich, dass ich nach dem Üben dieser Erkundungen auch DP und Dyxtra lernen kann. Vielen Dank für Ihre Beziehung. Na dann.

Einführung in Algorithmen mit Java --Search (Bit Full Search)

Artikelübersicht

Bit vollständige Suche

main.java

`main.java`