Introduction aux algorithmes avec java --Search (bit full search)

Résumé de l'article

Il s'agit d'une série d'articles que j'ai compilés dans mon étude et mon mémo. Le quatrième. Ceci est une suite de cet article. Introduction aux algorithmes avec java-Search (Width Priority Search) Dans cet article

--bits recherche complète

Je vais étudier sur. Je suis sûr que vous verrez l'explication du calcul, alors venez.

recherche peu complète

J'avais l'habitude de penser que c'était une recherche binaire, mais cela semble différent. Découvrons de quel type de recherche il s'agit.

Je l'ai cherché. Cela semble être le moyen de rechercher tous les modèles quand il y a (probablement) deux choix pour chacun dans un ensemble. Est-ce difficile à comprendre? Je vais présenter un exemple tout de suite.

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

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

Comme ce problème, l'endroit où se trouve le i-ème livre ** «acheter / ne pas acheter» ** est comme le problème de recherche de bits complet. Il y a N livres de référence, et chaque livre a deux choix, "acheter / ne pas acheter", il est donc nécessaire de rechercher 2 ^ N fois. ↓

C'est vrai. Il y a 2 choix pour chacun des N livres, donc il y a 2 ^ N façons. Ici, si acheter = 1 et non acheter = 0, il peut être exprimé en ticks binaires.

En supposant que N, N-1, N-2, ..., 3,2,1 à partir du haut du chiffre, par exemple, lorsque N = 5, "01001" signifie acheter les 4e et 1er livres.

Soit dit en passant, mathématiquement parlant, on peut dire que c'est «le nombre de sous-ensembles pour l'achat de N livres de référence». Si l'ensemble de N livres de référence est {1,2,3, ..., N-1, N}, par exemple, le sous-ensemble lors de l'achat des premier et troisième livres peut être exprimé par {1,3}. Droite. Ce "nombre de sous-ensembles" peut également être exprimé par 2 ^ N. Vous pouvez appliquer les deux choix «ajouter ou non au sous-ensemble» à chaque livre de référence (le livre de référence à ce moment est appelé mathématiquement l'original ou l'élément).

Par exemple, le sous-ensemble de l'achat de 3 livres est le suivant.

{000}・ ・ ・ Je n'achète pas un seul livre
{001}・ ・ ・ Achetez uniquement le premier livre
{010}・ ・ ・ Achetez uniquement le deuxième livre
{011}・ ・ ・ Achetez les premier et deuxième livres
{100}・ ・ ・ N'achetez que le troisième livre
{101}・ ・ ・ Achetez les 1er et 3ème livres
{110}・ ・ ・ Achetez les 2e et 3e livres
{111}・ ・ ・ Achetez les 3 livres

Vous pouvez voir qu'il y a exactement 2 ^ 3 = 8 façons.

Jetons un œil à un exemple de réponse de java.

[Exemple de réponse]

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);

		//Nombre d'ouvrages de référence
		int n = sc.nextInt();

		//Nombre d'algorithmes que vous souhaitez apprendre
		int m = sc.nextInt();

		//Compréhension de la cible d'acquisition
		int x = sc.nextInt();

		//Prix du nième livre de référence
		int[] costs = new int[n];

		//Meilleure compréhension du m-ième algorithme dans le n-ième ouvrage de référence
		int[][] a = new int[n][m];

		//Réception d'entrée
		for (int i = 0; i < n; i++) {
			costs[i] = sc.nextInt();
			for (int j = 0; j < m; j++) {
				a[i][j] = sc.nextInt();
			}
		}

		//Compréhension du niveau du m-ème algorithme, variable tmp du coût du livre de référence, variable à retenir du coût du livre de référence pour chaque boucle, variable indiquant si l'acquisition de l'algorithme a été réalisée
		int[] aTmp = new int[m];
		int costTmp = 0;
		List<Integer> costsSave = new ArrayList<>();
		boolean mastered = true;

		/*
		 *Recherche peu complète à partir d'ici
		 */
		for (int i = 0; i < 1 << n; i++) {
			//toutes les boucles de recherche complète de bits

			for (int j = 0; j < n; j++) {
				//Déterminer quel livre de référence acheter pour chaque boucle(Acheter ou non le jème livre)

				if ((1 & i >> j) == 1) {
					//Je me suis fait prendre ici=Ajouter pour acheter(jth achat de livre)

					for (int h = 0; h < m; h++) {
						//Meilleure compréhension du mth algorithme lors de l'achat du jth reference book
						aTmp[h] += a[j][h];
					}

					//Prix du jème livre
					costTmp += costs[j];
				}
			}

			//Depuis que j'ai fini d'acheter le livre de référence, je jugerai si je peux me souvenir de l'algorithme et garder le prix
			for (int h = 0; h < m; h++) {
				if (aTmp[h] < x) {
					//Si vous ne vous souvenez même pas d'un algorithme, NG
					mastered = false;
					break;
				}
			}

			if (mastered) {
				//Stocker temporairement le prix total
				costsSave.add(costTmp);
			}

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

		//Affiche la plus petite valeur de la liste. Si la liste est nulle"-1"Production
		int ans = Integer.MAX_VALUE;
		if (costsSave.isEmpty()) {
			ans = -1;
		} else {
			for (int cost : costsSave) {
				if (ans > cost) {
					ans = cost;
				}
			}
		}

		System.out.println(ans);

	}
}

C'est comme ça. D'une manière ou d'une autre, lorsque j'écris habituellement en java, j'utilise deux fois des symboles inconnus. "Rechercher tous les bits d'ici" for (int i = 0; i < 1 << n; i++) Quand, "Je me suis fait prendre ici = ajouté à la cible d'achat (jème achat de livre)" if ((1 & i >> j) == 1) n'est-ce pas.

"&" "<<" ">>" sont appelés "opérateurs de bits". Pour un traitement détaillé, veuillez gg et expliquer brièvement. "&" Est un produit logique, et "<<" et ">>" servent à déplacer la chaîne de bits vers la droite ou la gauche.

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

Avez-vous vu le décalage vers la droite ou vers la gauche, qui prend le produit logique pour chaque bit? J'irai légèrement ici.

Expliquons le code. Tout d'abord for (int i = 0; i < 1 << n; i++) c'est ici. Notez la partie condition de répétition de cette instruction for, ʻi <1 << n`. Tout d'abord, le premier symbole "<" (celui à droite de i) est une inégalité et semble être correct. Ainsi, le «<<» dans «1 << n» est l'opérateur de bits (à proprement parler, l'opérateur de décalage). Cela signifie «1 << n», mais cela signifie ** «décaler 1 vers la gauche n fois» **. Par exemple, si vous décalez 1 vers la gauche une fois, ce sera "10" (exprimé en binaire, qui est 2 en décimal).

De même Si vous décalez 1 vers la gauche deux fois, ce sera "100" (exprimé en notation binaire. C'est 4 (= 2 ^ 2) en notation décimale). Si vous décalez 1 vers la gauche trois fois, vous obtenez "1000" (exprimé en binaire, 8 (= 2 ^ 3) en décimal). Si vous décalez 1 vers la gauche quatre fois, vous obtenez "10000" (exprimé en binaire, 16 (= 2 ^ 4) en décimal).

image

En premier lieu, en ce qui concerne le nombre total de recherches cette fois, je voulais réfléchir à 2 ^ N façons car c'est la même chose que d'acheter ou de ne pas acheter pour n livres de référence. En d'autres termes, si vous réécrivez cette instruction for, for (int i = 0; i < Math.pow(2,n); i++) Peut également être réécrit. Avez-vous compris d'une manière ou d'une autre?

Allons-y ensuite.

if ((1 & i >> j) == 1) C'était difficile à comprendre, n'est-ce pas? .. Si vous traduisez les parenthèses de l'instruction if en japonais, c'est "si le produit logique de ** 1 et i >> j est égal à 1 **".

Par exemple, disons i = 5 et j = 2. (En parlant de ce problème, nous sommes en train d'envisager la 5ème recherche et l'achat du 3ème livre.) Si vous convertissez 5 en nombre binaire, ce sera 0101, et si vous le décalez deux fois vers la droite, cela ressemblera à ce qui suit.

Alors, prenez le produit logique de ceci et 1 (0001). Savez-vous que prendre le produit logique de 1 détermine ** si le dernier chiffre est 1 ou non **? En décalant deux fois et le dernier chiffre étant 1, en d'autres termes, en regardant deux à gauche du dernier chiffre pour voir s'il est 1. En d'autres termes, il est jugé si le jième chiffre à partir du bas est 1. S'il vaut 1, ce sera la cible d'achat.

Rechercher tous les modèles avec l'instruction for dans "Rechercher tous les bits d'ici", La phrase suivante "Déterminer quel livre de référence acheter pour chaque boucle (s'il faut acheter le jème livre)" spécifie le livre à acheter avec ce modèle.

Est-ce un peu difficile? Suivons le processus en mettant un exemple d'entrée concret à titre d'essai.

【Exemple d'entrée】

3 3 10
60 2 2 4
70 8 7 9
50 2 3 9

n = 3 , m = 3 , x = 10 0ème coût du livre, compréhension de l'algorithme 0,1,2 Coût du premier livre, compréhension de l'algorithme 0,1,2 Coût du deuxième livre, compréhension de l'algorithme 0,1,2 C'était l'ordre de. Il est facile à comprendre et compte à partir de 0 départ.

Alors recherchons tous les bits. Puisque n = 3, La boucle de "recherche de bits complète à partir d'ici" for(int i = 0 ; i < 1 << 3 ; i++) Ainsi, 1 << 3 décale 0001 vers la gauche trois fois, il devient donc 1000. C'est huit. C'est exactement 2 ^ 3.

Regardons i = 0 à i = 7 dans l'ordre. Je vais le convertir en nombre binaire le cas échéant. Le chiffre que vous regardez avec j est affiché en gras.

Lorsque i = 0 (000) Lorsque j = 0 (i = 00 0 </ b>) Si ((1 & 000 >> 0) == 1) n'est pas, alors n'achetez pas le 0ème livre Lorsque j = 1 (i = 0 0 </ b> 0) Je n'achète pas le premier livre car ce n'est pas ʻif ((1 & 000 >> 1) == 1) Lorsque j = 2 (i = <b> 0 </ b> 00) Si ((1 & 000 >> 2) == 1)n'est pas, alors n'achetez pas le deuxième livre Quand i = 1 (001) Lorsque j = 0 (i = 00 <b> 1 </ b>) ʻSi ((1 & 001 >> 0) == 1), alors achetez le 0ème livre Lorsque j = 1 (i = 0 0 </ b> 1) ʻSi ((1 & 001 >> 1) == 1) ʻ n'est pas, donc je n'achèterai pas le premier livre Lorsque j = 2 (i = 0 </ b> 01) Si ((1 & 001 >> 2) == 1) n'est pas, donc je n'achèterai pas le deuxième livre Quand i = 2 (010) Lorsque j = 0 (i = 01 0 </ b>) Si ((1 & 010 >> 0) == 1) n'est pas, alors n'achetez pas le 0ème livre Lorsque j = 1 (i = 0 1 </ b> 0) ʻSi ((1 & 010 >> 1) == 1) , alors achetez le premier livre Lorsque j = 2 (i = <b> 0 </ b> 10) Si ((1 & 010 >> 2) == 1)n'est pas, donc je n'achèterai pas le deuxième livre Quand i = 3 (011) Lorsque j = 0 (i = 01 <b> 1 </ b>) ʻSi ((1 & 011 >> 0) == 1), alors achetez le 0ème livre Lorsque j = 1 (i = 0 1 </ b> 1) ʻSi ((1 & 011 >> 1) == 1) , alors achetez le premier livre Lorsque j = 2 (i = <b> 0 </ b> 11) Si ((1 & 011 >> 2) == 1)n'est pas, donc je n'achèterai pas le deuxième livre Quand i = 4 (100) Lorsque j = 0 (i = 10 <b> 0 </ b>) ʻSi ((1 & 100 >> 0) == 1)n'est pas, alors n'achetez pas le 0ème livre Lorsque j = 1 (i = 1 0 </ b> 0) Je n'achète pas le premier livre parce que ce n'est pas ʻif ((1 & 100 >> 1) == 1) Lorsque j = 2 (i = <b> 1 </ b> 00) ʻSi ((1 & 100 >> 2) == 1), alors achetez le deuxième livre Quand i = 5 (101) Lorsque j = 0 (i = 10 1 </ b>) ʻSi ((1 & 101 >> 0) == 1) , alors achetez le 0ème livre Lorsque j = 1 (i = 1 <b> 0 </ b> 1) Je n'achète pas le premier livre parce que ce n'est pas ʻif ((1 & 101 >> 1) == 1) Lorsque j = 2 (i = 1 </ b> 01) ʻSi ((1 & 101 >> 2) == 1) , alors achetez le deuxième livre Quand i = 6 (110) Lorsque j = 0 (i = 11 <b> 0 </ b>) ʻSi ((1 & 110 >> 0) == 1) n'est pas, alors n'achetez pas le 0ème livre Lorsque j = 1 (i = 1 1 </ b> 0) ʻSi ((1 & 110 >> 1) == 1) , alors achetez le premier livre Lorsque j = 2 (i = <b> 1 </ b> 10) ʻSi ((1 & 110 >> 2) == 1) , alors achetez le deuxième livre Quand i = 7 (111) Lorsque j = 0 (i = 11 1 </ b>) ʻSi ((1 & 111 >> 0) == 1) , alors achetez le 0ème livre Lorsque j = 1 (i = 1 <b> 1 </ b> 1) ʻSi ((1 & 111 >> 1) == 1) , alors achetez le premier livre Lorsque j = 2 (i = 1 </ b> 11) ʻSi ((1 & 111 >> 2) == 1) `, alors achetez le deuxième livre