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

Introduction

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)

Recommended Posts

[Python] Although it is a humanities, I will do my best to understand bit full search
I want to do it with Python lambda Django, but I will stop
python bit full search
I made a python library to do rolling rank
Full bit search with Python
I made a segment tree with python, so I will introduce it
What to do if there is a decimal in python json .dumps
I tried to make a calculator with Tkinter so I will write it
I want to do a monkey patch only partially safely in Python
I managed to do it because the custom of attaching a zip with a password to an email and saying "I will send you the password separately" is troublesome.
A super introduction to Python bit operations
I want to build a Python environment
A way to understand Python duck typing
I tried my best to return to Lasso
I went to "Summer is in full swing! Spark + Python + Data Science Festival".
I want to create a nice Python development environment for my new Mac
python Binary search It is surprisingly easy to implement bisect.bisect_left and bisect.bisect_right from 0
When I tried to create a virtual environment with Python, it didn't work
Creating a Python document generation tool because it is difficult to use sphinx
[I'm an IT beginner] I tried my best to implement Linux on Windows
Python program is slow! I want to speed up! In such a case ...
I tried my best to make an optimization function, but it didn't work.