[GO] [Python] Although it is a humanities, I will do my best to understand bit full search

Introduction

• Personal memo

https://qiita.com/gogotealove/items/11f9e83218926211083a This article also explains the bit full search very carefully. However, I couldn't catch up with my understanding just by reading it with my own mind in the humanities, so I wrote the code myself and tried to understand it one by one.

code

Tangerine apple grape.py

#reference:https://qiita.com/gogotealove/items/11f9e83218926211083a

# -example- 
#Mandarin oranges (100 yen), apples (200 yen) and grapes (300 yen)
#There was one each at the fruit shop.
#There is 300 yen in the wallet,
#List all possible shopping patterns.

# -Way of thinking-
#Calculate the total amount for all shopping patterns and
#List the ones that cost less than 300 yen

# 2~3 =List the ones under 300 yen from 8 patterns

money = 300
item = (("Mandarin orange",100),("Apple",200),("Grape",300))

n = len(item)

#Buy or not buy each item
#"Whether each digit of the binary number is 0 or 1(From the left, oranges, apples, grapes)」
#Expressed in, the table is as follows.

# -Decimal number notation-　-Binary notation-　-Things to buy-
#0 000 don't buy anything
#1 001 grapes
#2 010 apples
#3 011 apples+Grape
#4 100 oranges
#5 101 mandarin oranges+Grape
#6 110 mandarin oranges+Apple
#7 111 mandarin oranges+Apple+Grape

#All pattern loop
for i in range(2 ** n):
    bag = []
    total = 0

    #Loop for the number of items
    for j in range(n):
        #Shift to the right in order and check the least significant bit
        #If the 0th digit from the bottom is 1, then grapes are included
        #If the first digit from the bottom is 1, it contains apples
        #If the second digit from the bottom is 1, it will contain oranges

        #Start checking from the far right of the binary number

        # ex)i = 6、j =If 0(Grape check)
        #When the binary number "110" of 6 is shifted to the right by 0 bits, it becomes "110".
        #If the lowest value is ORed with 1, it will be false, so "no grapes"

        # ex)i = 6、j =In case of 1(Apple check)
        #When the binary number "110" of 6 is shifted to the right by 1 bit, it becomes "011".
        #If the lowest value is ORed with 1, it will be true, so "with apples"

        # ex)i = 6、j =In case of 2(Mandarin orange check)
        #When the binary number "110" of 6 is shifted right by 2 bits, it becomes "001".
        #If the lowest value is ORed with 1, it will be true, so "with oranges"
        if((i >> j) & 1):
            #If the flag is on, pack the fruit in the bag
            # [j](Elementnumberofitem)[0](Fruitname)
            bag.append(item[j][0])
            #Add to cumulative shopping amount
            # [1](Fruitamount)
            total += item[j][1]

    #When total is 300 or less, the total amount and the fruit name stored in the array bag are output.
    if(total <= money):
        print(total,bag)

def test():
    #Nth digit counting from the bottom when expressed in binary(Set the last digit to 0)But
    #The code to check if it is 1 is "(i >> n) &1 ".
    #This is "shift i n times to the right and 1(Binary number 001)And AND(Check if the least significant digit is 1 "
    #It turns out that.
    
    i = 5

    #101 when 5 is expressed in binary
    bin(i) 
    #Shift 5 to the right twice and 001
    bin(i >> 2)
    #5 is shifted to the right twice
    #The logical product of 1 is 1(=True)
    print((i >> 2) & 1)