Andrea Bianchini 2024.
18 Spartiti per Piano
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 by Andrea Bianchini 2024.")
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.
Maybe One Day
Andrea Bianchini 2024.
Un Unico Dio
Un unico Dio
Alto lo sguardo orgoglioso
o segno di grave malattia.
Abbiamo visto di tutto,
anche ciò che non c’era,
e non erano miraggi…
Abbiamo pregato ora la terra,
ora il sole, ora le stelle.
Poi vennero gli Dei,
prima animali e uomini,
poi uomini, poi spiriti ed angeli,
infine un unico Dio.
La civiltà ci ha portato a questo
insieme alla teologia,
la filosofia e la scienza.
Quale sarà il nostro prossimo Creatore ?
Un unico Dio per tutte le religioni ?
Andrea Bianchini 2024.
Andrea Bianchini 2024.
Soft Air
You Are Everywhere
Andrea Bianchini 2024.
Sometime My Mood
Andrea Bianchini 2024.
Heart is the Greatest Master of Love
Andrea Bianchini 2024.
Total Love for an Unknown Woman
Andrea Bianchini 2024.