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.
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