# 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
4000Execution 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.