Subset Sum Problem

Alt Küme Toplamı Problemi (Subset Sum Problem) icin bir cozum yaklasimi. Bu algoritma eksiksiz bir tarama sunar.
mail@pastecode.io avatar
unknown
python
a year ago
1.1 kB
27
Indexable
Never
"""
Alt Küme Toplamı Problemi
(Subset Sum Problem)
icin bir cozum yaklasimi.

Bu algoritma eksiksiz bir tarama sunar.
"""


import random
import os
os.system('cls')

#manuel degisken(ler) ---->

# L: eleman sayisi
# (pc icin monothread'de
# L > 15 tavsiye edilmez)
L = 10

# <---- manuel degisken(ler)


a = []
g = []
t = 0

for i in range(L):
    a.append(random.randint(-L,+L))

print("a =", a)
print()

zero =""
for i in range(L):
    zero += "0"

""" cok elemanli kumelerde
    range araliklara bolunerek
    multithread yapilabilir """
for i in range(2**L):
    b = bin(i)
    b = b[2:]
    b = zero[0:L-len(b)] + b
    
    t = 0
    g = []
    idx = 0

    """ hiz icin b yerine 1'leri
    baska bir diziye indisleriyle
    degistirmek dusunulebilir """
    for j in range(len(b)):
        if b[j]=="1":
            t+=a[j]
            g.append(a[j])
    if t == 0:
        if len(g)>1:
            try:
                idx = g.index(0)
            except:
                idx = -1
            
            if idx == -1:
                print(g)