bit全探索の確認

Python de アルゴリズム（bit全探索）
https://qiita.com/gogotealove/items/11f9e83218926211083a

この記事の例題1を自分なりに整理した

main.py

money = 300
item = (("みかん", 100), ("りんご", 200), ("ぶどう", 300))
n = len(item)
for i in range(2**n):
    bag = []
    total = 0
    for j in range(n):
        if((i >> j) & 1):
            bag.append(item[j][0])
            total += item[j][1]
    if(total <= money):
        print(total, bag)

出力

0 []
100 ['みかん']
200 ['りんご']
300 ['みかん', 'りんご']
300 ['ぶどう']

i >> j : i を　右にjビットシフト(iを(1/2)^jする)
i << j : iを左にjビットシフト(iを2^jする)

n=3,i = [0:7], j=[0:2]において

i = 0, j=0のとき　

i >>j = 0 0と1の論理積は0なので0 i = 0, j=1のとき i>>j = 0 0と1の論理積は0なので0 i = 0,j=1 i=0, j=2 のときも同様に0

i=1, j=0のとき

1 >>0 = 1 1と1の論理積は1なので1 よってbag.append(item[0][0]), total += item[0][1], total = 100 <= 300 なので print 100 ['みかん'] i=1, j=1のとき 1 >> 1 = 0.5 = 0 0と1の論理積は0なので0 i=1, j=2のとき 1>>2 = 0

i=2, j=0のとき

2>>0 = 2 i=2, j=1のとき 2>>1 = 1 1と1の論理積は1 よってbag.append(item[1][0]) = "りんご", total += item[1][1],total=200<=300　なので print 200['りんご'] i=2, j=2のとき 2>>2 = 0

i=3, j=0のとき

3>>0 = 3 i=3, j=1のとき 3>>1 = 1 よって bag.append(item[1][0]) = りんご, total += item[1][1]

i=4, j=1のとき

4 >> 1 = 2

i=4, j=2のとき

4 >> 2 = 1
よって bag.append(item[2][0])= "ぶどう", total += item[2][1], total = 300 <= 300 なので print 300['ぶどう']

i=5, j=0のとき

5>>0 =5 5&1 = 1

i=5, j=1のとき

5 >>1 =2

i=5, j=2のとき　

5>>2 = 1 1&1 = 1 total= 100 + 300 = 400 > 300　より不適

i=6, j=0のとき

6>>0 = 6 6&1 = 0

i=6, j=1のとき

6>>1 = 3 3&1 = 1

i=6, j=2のとき

6>>2 = 1 1&1 = 1
total = 200 + 300 = 500 > 300 より不適

i=7, j=0のとき

7>>0 = 7 7&1=1

i=7, j=1のとき

7>>1 = 3 3&1=1

i=7, j=2のとき

7>>2 = 0
total = 100 + 200　なので print 300['みかん']['りんご']