Introduction to algorithms with java --Search (bit full search)

Article summary

This is a series of articles that I have compiled in my study and memo. The fourth. This is a continuation of this article. Introduction to algorithms in java-Search (breadth-first search) In this article

--bit full search

I will study about. I'm sure you'll see the explanation of the calculation, so please come.

bit full search

I used to think that this was a binary search, but it seems different. Let's find out what kind of search it is.

I looked it up. It seems to be the way to search all patterns when there are (probably) two choices for each one in a set. Is it difficult to understand? I will introduce an example at once.

Example: 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

Like this problem, the place where you have two choices of ** "buy / do not buy" ** for the i-th book is like the bit full search problem. There are N reference books, and each book has two choices, "buy / not buy", so it is necessary to search 2 ^ N times. ↓

That's right. There are 2 choices for each of the N books, so there are 2 ^ N ways. Here, if buy = 1 and not buy = 0, it can be expressed as a binary tic.

Assuming that the first volume is N, N-1, N-2, ..., 3,2,1 from the upper digit, for example, when N = 5, "01001" means to buy the 4th and 1st books.

By the way, mathematically speaking, it can be said to be "the number of subsets that should be purchased for N reference books." If the set of N reference books is {1,2,3, ..., N-1, N}, for example, the subset when buying the first and third books can be expressed as {1,3}. Right. This "number of subsets" can also be expressed as 2 ^ N. You can apply the two choices of "add or not to the subset" to each reference book (the reference book at this time is mathematically called the original or element).

For example, the subset of whether to purchase 3 books is as follows.

{000}・ ・ ・ I don't buy a single book
{001}・ ・ ・ Buy only the first book
{010}・ ・ ・ Buy only the second book
{011}・ ・ ・ Buy the first and second books
{100}・ ・ ・ Buy only the third book
{101}・ ・ ・ Buy the 1st and 3rd books
{110}・ ・ ・ Buy the 2nd and 3rd books
{111}・ ・ ・ Buy all 3 books

You can see that there are exactly 2 ^ 3 = 8 ways.

Let's take a look at an example answer from java.

[Answer example]

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

		//Number of reference books
		int n = sc.nextInt();

		//Number of algorithms you want to learn
		int m = sc.nextInt();

		//Acquisition goal comprehension
		int x = sc.nextInt();

		//Price of the nth reference book
		int[] costs = new int[n];

		//Increased comprehension of the m-th algorithm in the n-th reference book
		int[][] a = new int[n][m];

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

		//Understanding of the m-th algorithm, tmp variable of reference book cost, variable to remember reference book cost for each loop, variable of whether algorithm acquisition was achieved
		int[] aTmp = new int[m];
		int costTmp = 0;
		List<Integer> costsSave = new ArrayList<>();
		boolean mastered = true;

		/*
		 *Bit full search from here
		 */
		for (int i = 0; i < 1 << n; i++) {
			//The whole loop of bit full search

			for (int j = 0; j < n; j++) {
				//Determining which reference book to buy for each loop(Whether to buy the jth book)

				if ((1 & i >> j) == 1) {
					//I got caught here=Add to buy(jth book purchase)

					for (int h = 0; h < m; h++) {
						//Increased understanding of the mth algorithm when buying the jth reference book
						aTmp[h] += a[j][h];
					}

					//Price of the jth book
					costTmp += costs[j];
				}
			}

			//Since I finished buying the reference book, I will judge whether I can remember the algorithm and keep the price
			for (int h = 0; h < m; h++) {
				if (aTmp[h] < x) {
					//NG if you don't remember even one algorithm
					mastered = false;
					break;
				}
			}

			if (mastered) {
				//Temporarily store the total price
				costsSave.add(costTmp);
			}

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

		//Output the smallest value in list. If the list is null"-1"Output
		int ans = Integer.MAX_VALUE;
		if (costsSave.isEmpty()) {
			ans = -1;
		} else {
			for (int cost : costsSave) {
				if (ans > cost) {
					ans = cost;
				}
			}
		}

		System.out.println(ans);

	}
}

It is like this. Somehow, when I usually write java, I use unfamiliar symbols about twice. "Search all bits from here" for (int i = 0; i < 1 << n; i++) When, "I got caught here = added to the purchase target (jth book purchase)" if ((1 & i >> j) == 1) is not it.

"&" "<<" ">>" are called "bit operators". For detailed processing, please gg and explain briefly. "&" Is a logical product, and "<<" and ">>" are for shifting the bit string to the right or left.

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

Did you see the shift to the right or left, which takes the logical product for each bit? I will go lightly here.

Let's explain the code. First of all for (int i = 0; i < 1 << n; i++) it's here. Notice the repeat condition part of this for statement, ʻi <1 << n. First of all, the first symbol "<" (the one to the right of i) is an inequality sign and seems to be correct. So, the "<<" in 1 << nis the bit operator (strictly speaking, the shift operator). It means1 << n`, but it means " shift 1 to the left n times ". For example, if you shift 1 to the left once, it will be "10" (expressed in decimal, which is 2 in decimal).

Similarly Shifting 1 to the left twice gives "100" (expressed in decimal, 4 (= 2 ^ 2) in decimal). Shifting 1 to the left three times gives "1000" (expressed in decimal, 8 (= 2 ^ 3) in decimal). Shifting 1 to the left four times gives "10000" (expressed in decimal, 16 (= 2 ^ 4) in decimal).

image

In the first place, as for the number of total searches this time, I wanted to think about 2 ^ N ways because it is the same as buying or not buying for n reference books. In other words, if you rewrite this for statement, for (int i = 0; i < Math.pow(2,n); i++) Can also be rewritten. Did you understand somehow?

Let's go next.

if ((1 & i >> j) == 1) It was hard to understand this, wasn't it? .. If you translate the parentheses of the if statement into Japanese, it is "whether the logical product of ** 1 and i >> j is equal to 1 **".

For example, let's say i = 5 and j = 2. (Speaking of this problem, we are in the process of considering the 5th search and the purchase of the 3rd book.) Converting 5 to binary is 0101, and shifting it to the right twice gives the following feeling.

Then, take the logical product of 1 (0001) with this. Do you know that taking a logical product with 1 determines ** whether the last digit is 1 or not **? Shifting twice and the last digit being 1, in other words, looking two left from the last digit to see if it is 1. In other words, it is judged whether the jth digit from the bottom is 1. If it is 1, it will be the target of purchase.

Search for all patterns with the for statement in "Search all bits from here", The following for sentence "Determining which reference book to buy for each loop (whether to buy the jth book)" identifies the book to buy with that pattern.

Is it a little difficult? Let's follow the process by putting a concrete input example as a trial.

【Input example】

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

n = 3 , m = 3 , x = 10 0th book cost, algorithm comprehension 0,1,2 Cost of the first book, understanding of the algorithm 0,1,2 Cost of the second book, understanding of the algorithm 0,1,2 It was the order of. It is easy to understand and counts from 0 start.

Then let's search all bits. Since n = 3, The loop of "bit full search from here" for(int i = 0 ; i < 1 << 3 ; i++) So, 1 << 3 shifts 0001 to the left three times, so it becomes 1000. That is eight. It is exactly 2 ^ 3.

Let's look at i = 0 to i = 7 in order. I will convert it to a binary number as appropriate. The digit you are looking at in j is shown in bold.

When i = 0 (000) When j = 0 (i = 00 0 </ b>) ʻIf ((1 & 000 >> 0) == 1) is not, so do not buy the 0th book When j = 1 (i = 0 <b> 0 </ b> 0) I don't buy the first book because it's not ʻif ((1 & 000 >> 1) == 1) When j = 2 (i = 0 </ b> 00) ʻIf ((1 & 000 >> 2) == 1) is not, so don't buy the second book When i = 1 (001) When j = 0 (i = 00 <b> 1 </ b>) ʻIf ((1 & 001 >> 0) == 1), so buy the 0th book When j = 1 (i = 0 0 </ b> 1) I don't buy the first book because it's not ʻif ((1 & 001 >> 1) == 1) When j = 2 (i = <b> 0 </ b> 01) I don't buy the second book because it's not ʻif ((1 & 001 >> 2) == 1) When i = 2 (010) When j = 0 (i = 01 0 </ b>) ʻIf ((1 & 010 >> 0) == 1) is not, so do not buy the 0th book When j = 1 (i = 0 <b> 1 </ b> 0) ʻIf ((1 & 010 >> 1) == 1) , so buy the first book When j = 2 (i = 0 </ b> 10) I don't buy the second book because it's not ʻif ((1 & 010 >> 2) == 1) When i = 3 (011) When j = 0 (i = 01 <b> 1 </ b>) ʻIf ((1 & 011 >> 0) == 1), so buy the 0th book When j = 1 (i = 0 1 </ b> 1) ʻIf ((1 & 011 >> 1) == 1) , so buy the first book When j = 2 (i = <b> 0 </ b> 11) I don't buy the second book because it's not ʻif ((1 & 011 >> 2) == 1) When i = 4 (100) When j = 0 (i = 10 0 </ b>) ʻIf ((1 & 100 >> 0) == 1) is not, so do not buy the 0th book When j = 1 (i = 1 <b> 0 </ b> 0) I don't buy the first book because it's not ʻif ((1 & 100 >> 1) == 1) When j = 2 (i = 1 </ b> 00) ʻIf ((1 & 100 >> 2) == 1), so buy the second book When i = 5 (101) When j = 0 (i = 10 <b> 1 </ b>) ʻIf ((1 & 101 >> 0) == 1) , so buy the 0th book When j = 1 (i = 1 0 </ b> 1) I don't buy the first book because it's not ʻif ((1 & 101 >> 1) == 1) When j = 2 (i = <b> 1 </ b> 01) ʻIf ((1 & 101 >> 2) == 1), so buy the second book When i = 6 (110) When j = 0 (i = 11 0 </ b>) ʻIf ((1 & 110 >> 0) == 1) is not, so do not buy the 0th book When j = 1 (i = 1 <b> 1 </ b> 0) ʻIf ((1 & 110 >> 1) == 1) , so buy the first book When j = 2 (i = 1 </ b> 10) ʻIf ((1 & 110 >> 2) == 1), so buy the second book When i = 7 (111) When j = 0 (i = 11 <b> 1 </ b>) ʻIf ((1 & 111 >> 0) == 1) , so buy the 0th book When j = 1 (i = 1 1 </ b> 1) ʻIf ((1 & 111 >> 1) == 1) , so buy the first book When j = 2 (i = <b> 1 </ b> 11) ʻIf ((1 & 111 >> 2) == 1) , so buy the second book