[PYTHON] Confirmer la recherche de bits complète

Python de algorithme (recherche complète de bits) https://qiita.com/gogotealove/items/11f9e83218926211083a

J'ai organisé l'exemple 1 de cet article à ma manière

main.py

money = 300
item = (("Mandarine", 100), ("pomme", 200), ("Grain de raisin", 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)

production

0 []
100 ['Mandarine']
200 ['pomme']
300 ['Mandarine', 'pomme']
300 ['Grain de raisin']

i >> j: je décale j vers la droite (i est (1/2) ^ j) i << j: décale i vers la gauche de j bits (fixe i à 2 ^ j)

À n = 3, i = [0: 7], j = [0: 2]

Lorsque i = 0, j = 0

i >> j = 0 Le produit logique de 0 et 1 est 0, donc 0 i = 0, quand j = 1 i >> j = 0 Le produit logique de 0 et 1 est 0, donc 0 i = 0, j = 1 i = De même lorsque 0, j = 2

Lorsque i = 1, j = 0

1 >> 0 = 1 Puisque le produit logique de 1 et 1 est 1, 1 donc bag.append (item [0] [0]), total + = item [0] [1], total = 100 <= 300, donc imprimer 100 ['Mikan'] Quand i = 1, j = 1 1 >> 1 = 0.5 = 0 Le produit logique de 0 et 1 est 0, donc 0 quand i = 1, j = 2 1 >> 2 = 0

Quand i = 2, j = 0

2 >> 0 = 2 Quand i = 2, j = 1 2 >> 1 = 1 Le produit logique de 1 et 1 est 1 Par conséquent bag.append (item [1] [0]) = "apple", total + = élément [1] [1], total = 200 <= 300, donc imprimez 200 ['pomme'] i = 2, j = 2 2 >> 2 = 0

Lorsque i = 3, j = 0

3 >> 0 = 3 quand i = 3, j = 1 3 >> 1 = 1 Par conséquent bag.append (item [1] [0]) = apple, total + = item [1] [1]

Lorsque i = 4, j = 1

4 >> 1 = 2

Quand i = 4, j = 2

4 >> 2 = 1 Par conséquent, bag.append (item [2] [0]) = "raisin", total + = item [2] [1], total = 300 <= 300, donc imprimez 300 ['raisin']

Lorsque i = 5, j = 0

5>>0 =5 5&1 = 1

Lorsque i = 5, j = 1

5 >>1 =2

Quand i = 5, j = 2

5 >> 2 = 1 1 & 1 = 1 total = 100 + 300 = 400> 300 Plus inadapté

Lorsque i = 6, j = 0

6>>0 = 6 6&1 = 0

Lorsque i = 6, j = 1

6>>1 = 3 3&1 = 1

Quand i = 6, j = 2

6>>2 = 1 1&1 = 1 Moins approprié que le total = 200 + 300 = 500> 300

Lorsque i = 7, j = 0

7>>0 = 7 7&1=1

Lorsque i = 7, j = 1

7>>1 = 3 3&1=1

Quand i = 7, j = 2

7>>2 = 0 Puisque total = 100 + 200, imprimez 300 ['Mikan'] ['Apple']