Python de algorithm (bit full search) https://qiita.com/gogotealove/items/11f9e83218926211083a
I organized Example 1 of this article in my own way
main.py
money = 300
item = (("Mandarin orange", 100), ("Apple", 200), ("Grape", 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)
output
0 []
100 ['Mandarin orange']
200 ['Apple']
300 ['Mandarin orange', 'Apple']
300 ['Grape']
i >> j: i shift j to the right (i is (1/2) ^ j) i << j: shift i to the left by j bits (set i to 2 ^ j)
At n = 3, i = [0: 7], j = [0: 2]
i >> j = 0 The logical product of 0 and 1 is 0, so 0 i = 0, when j = 1 i >> j = 0 The logical product of 0 and 1 is 0, so 0 i = 0, j = 1 i = Similarly when 0, j = 2
1 >> 0 = 1 The logical product of 1 and 1 is 1, so 1 Therefore bag.append (item [0] [0]), total + = item [0] [1], total = 100 <= 300, so print 100 ['Mikan'] When i = 1, j = 1 1 >> 1 = 0.5 = 0 The logical product of 0 and 1 is 0, so 0 when i = 1, j = 2 1 >> 2 = 0
2 >> 0 = 2 When i = 2, j = 1 2 >> 1 = 1 The logical product of 1 and 1 is 1, so bag.append (item [1] [0]) = "apple", total + = item [1] [1], total = 200 <= 300, so print 200 ['apple'] i = 2, j = 2 2 >> 2 = 0
3 >> 0 = 3 when i = 3, j = 1 3 >> 1 = 1 Therefore bag.append (item [1] [0]) = apple, total + = item [1] [1]
4 >> 1 = 2
4 >> 2 = 1 Therefore, bag.append (item [2] [0]) = "grape", total + = item [2] [1], total = 300 <= 300, so print 300 ['grape']
5>>0 =5 5&1 = 1
5 >>1 =2
5 >> 2 = 1 1 & 1 = 1 total = 100 + 300 = 400> 300 More unsuitable
6>>0 = 6 6&1 = 0
6>>1 = 3 3&1 = 1
6>>2 = 1 1&1 = 1 Less suitable than total = 200 + 300 = 500> 300
7>>0 = 7 7&1=1
7>>1 = 3 3&1=1
7>>2 = 0 Since total = 100 + 200, print 300 ['Mikan'] ['Apple']
Recommended Posts