An Exact Algorithm of Polynomial Complexity for the Subset Sum Problem

# ssp.py - An Exact Algorithm of Polynomial Complexity for the Subset Sum Problem
#
# Andrea Bianchini, 2024, Common Creative CC BY-NC 4.0. 
#
# see also https://es-andreabianchini.it/ssp_eng.pdf
#

from random import randrange
import math

try:
    inp = open("input.txt","rt")
    n=int(inp.readline())
    c=int(inp.readline())
    wmin=int(inp.readline())
    wmax=int(inp.readline())
    inp.close()
    w=sorted([int(wmin+randrange(wmax-wmin)) for i in range(n)])
    c1=[0 for i in range(n)]
    sol=[0 for i in range(n)]
    bestsolu=[0 for i in range(n)]    
    niter=0
    bestsol=0
    bestsolk=0

except Exception:
    print(Exception)
    print()
    print("ssp, Andrea Bianchini, 2024, Common Creative CC BY-NC 4.0.")
    print("USAGE:")
    print("ssp")
    print("ssp reads input data from input.txt")
    print("WHERE input.txt is in the form:")
    print("n     # number of items")
    print("c     # capacity of the knapsack")
    print("wmin  # min item's weight")
    print("wmax  # max item's weight")
    print()
    
def solve():
    global n
    global c
    global w
    global bestsolu
    global sol
    global bestsol
        
        
    bestsol=0
    solvalue=0
    divi=1
    T=int(pow(2,n-1))
    while(T>1 and bestsol<c):
        t=0
        divi=1
        while(divi<int(pow(2,n)) and bestsol<c):

            #print(bin(T),bin(t),bestsol)


            sol=list(map(int,bin(t+int(T/divi))[2:].zfill(n)[::-1]))
            gt=sum([sol[i]*w[i] for i in range(n)])
            if (gt<=c):
                t=t+int(T/divi)

            divi*=2
            
            solvalue=gt
            if (bestsol<solvalue and solvalue<=c):
                bestsolu=list(map(int,bin(t)[2:].zfill(n)[::-1]))
                bestsol=solvalue

        T=int(T/2)
                   
    return

try:
    while(True):
        w=sorted([int(wmin+randrange(wmax-wmin)) for i in range(n)])
        
        print("n="+str(n))
        print("c="+str(c))
        print("wmin="+str(wmin))
        print("wmax="+str(wmax))
        print("w = ",w)
        print()

        bestsol=0
        
        solve()
    
        solvalue=sum([bestsolu[i]*w[i] for i in range(n)])

        print()
        print("Solution="+str(solvalue))
        print("Sol. Vector = ",bestsolu)
        print("Sol. Items = ",[w[i] for i in range(n) if bestsolu[i]==1])
        print("Hit return...")
        input()
except Exception:
    print(Exception.message)

input.txt file example:

50
10000
200
4000

Execution example:

n=50
c=10000
wmin=200
wmax=4000
w =  [257, 537, 580, 580, 664, 671, 688, 755, 844, 939, 953, 960, 1014, 1095, 1250, 1359, 1417, 1463, 1513, 1527, 1575, 1629, 1737, 1738, 1817, 1841, 1935, 1942, 2115, 2240, 2318, 2330, 2565, 2606, 2681, 2692, 2788, 3075, 3112, 3196, 3201, 3230, 3257, 3368, 3400, 3440, 3508, 3512, 3782, 3938]


Solution=10000
Sol. Vector =  [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Sol. Items =  [257, 580, 580, 664, 671, 688, 755, 844, 939, 953, 960, 1014, 1095]
Hit return...

n=50
c=10000
wmin=200
wmax=4000
w =  [293, 419, 439, 576, 635, 672, 978, 1031, 1063, 1120, 1229, 1285, 1288, 1446, 1660, 1800, 1978, 2014, 2033, 2034, 2040, 2148, 2185, 2193, 2201, 2479, 2506, 2521, 2540, 2553, 2585, 2673, 2799, 2976, 3051, 3089, 3287, 3371, 3379, 3390, 3438, 3581, 3613, 3661, 3696, 3753, 3763, 3766, 3834, 3836]


Solution=10000
Sol. Vector =  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Sol. Items =  [293, 2201, 2479, 2506, 2521]
Hit return...

https://es-andreabianchini.it/ssp_eng.pdf

Andrea Bianchini 2024.