Subset Sum Problem

Alt Küme Toplamı Problemi (Subset Sum Problem) icin bir cozum yaklasimi. Bu algoritma eksiksiz bir tarama sunar.
 avatar
unknown
python
2 years ago
1.1 kB
30
Indexable
"""
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)
Editor is loading...