[PYTHON] Bestätigen Sie die vollständige Suche

Python de Algorithmus (Bit vollständige Suche) https://qiita.com/gogotealove/items/11f9e83218926211083a

Ich habe Beispiel 1 dieses Artikels auf meine eigene Weise organisiert

main.py

money = 300
item = (("Mandarine", 100), ("Apfel", 200), ("Traube", 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)

Ausgabe

0 []
100 ['Mandarine']
200 ['Apfel']
300 ['Mandarine', 'Apfel']
300 ['Traube']

i >> j: ich verschiebe j nach rechts (i ist (1/2) ^ j) i << j: verschiebe i um j Bits nach links (setze i auf 2 ^ j)

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

Wenn i = 0 ist, ist j = 0

i >> j = 0 Das logische Produkt von 0 und 1 ist 0, also 0 i = 0, wenn j = 1 i >> j = 0 Das logische Produkt von 0 und 1 ist 0, also 0 i = 0, j = 1 i = In ähnlicher Weise ist bei 0 j = 2

Wenn i = 1 ist, ist j = 0

1 >> 0 = 1 Da das logische Produkt von 1 und 1 1 ist, ist 1 bag.append (Element [0] [0]), total + = item [0] [1], total = 100 <= 300, also drucke 100 ['Mikan'] Wenn i = 1, j = 1 1 >> 1 = 0,5 = 0 Das logische Produkt von 0 und 1 ist 0, also 0, wenn i = 1, j = 2 1 >> 2 = 0

Wenn i = 2, ist j = 0

2 >> 0 = 2 Wenn i = 2, j = 1 2 >> 1 = 1 Das logische Produkt von 1 und 1 ist 1. Daher bag.append (item [1] [0]) = "apple", total + = Punkt [1] [1], gesamt = 200 <= 300, also drucke 200 ['Apfel'] i = 2, j = 2 2 >> 2 = 0

Wenn i = 3 ist, ist j = 0

3 >> 0 = 3 wenn i = 3, j = 1 3 >> 1 = 1 Daher bag.append (Punkt [1] [0]) = Apfel, gesamt + = Punkt [1] [1]

Wenn i = 4, ist j = 1

4 >> 1 = 2

Wenn i = 4, ist j = 2

4 >> 2 = 1 Daher ist bag.append (Artikel [2] [0]) = "Traube", insgesamt + = Artikel [2] [1], gesamt = 300 <= 300, also drucken Sie 300 ['Traube']

Wenn i = 5, ist j = 0

5>>0 =5 5&1 = 1

Wenn i = 5, ist j = 1

5 >>1 =2

Wenn i = 5, ist j = 2

5 >> 2 = 1 1 & 1 = 1 gesamt = 100 + 300 = 400> 300 Ungeeigneter

Wenn i = 6, ist j = 0

6>>0 = 6 6&1 = 0

Wenn i = 6, ist j = 1

6>>1 = 3 3&1 = 1

Wenn i = 6, ist j = 2

6>>2 = 1 1&1 = 1 Weniger geeignet als insgesamt = 200 + 300 = 500> 300

Wenn i = 7, ist j = 0

7>>0 = 7 7&1=1

Wenn i = 7, ist j = 1

7>>1 = 3 3&1=1

Wenn i = 7, ist j = 2

7>>2 = 0 Da insgesamt = 100 + 200, drucken Sie 300 ['Mikan'] ['Apple']