Categoria: Ricerca Operativa

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

# kdiff.py
#
# 
# Questo programma risolve il seguente problema :
# Dato un insieme s di N numeri interi trovare
# tutte le coppie di interi la cui differenza è pari a K
#
# by Andrea Bianchini (2021)

from random import randint

N = 50
MIN = 1
MAX = 1000
K = randint(MIN,MAX/2)

s = [randint(MIN,MAX) for _ in range(N)]


def f(x,y):
    global K
    if abs(x-y)==K:
        return True
    else:
        return False
    
res =[]

for x in range(N-1):
    for y in range(x+1,N):
        if f(s[x],s[y]):
            res.append((s[x],s[y]))

print("s =",s)
print()
print("K = %d" %K)
print("coppie =",res)

Esempio 1:

s = [240, 662, 961, 108, 802, 232, 954, 99, 542, 775, 668, 988, 637, 96, 135, 549, 111, 678, 86, 596, 912, 13, 191, 516, 118, 88, 837, 632, 870, 843, 542, 569, 819, 579, 411, 154, 743, 89, 95, 686, 604, 503, 511, 859, 305, 671, 161, 510, 164, 906]

K = 10
coppie = [(108, 118), (99, 89), (668, 678), (96, 86), (569, 579), (154, 164)]
>>> 

Esempio 2:

s = [327, 847, 660, 722, 431, 287, 79, 542, 354, 514, 703, 522, 764, 75, 904, 789, 103, 801, 929, 884, 964, 818, 992, 458, 369, 900, 239, 671, 120, 904, 421, 342, 403, 314, 495, 794, 119, 140, 810, 237, 333, 639, 676, 705, 134, 802, 528, 20, 452, 2]

K = 105
coppie = [(239, 134), (342, 237), (810, 705)]
>>> 

# pulp1.py
#
# Risoluzione di un problema di programmazione lineare
# tramite la libreria PuLP.
#
# definizione problema by https://www3.diism.unisi.it/~agnetis/esesvolti.pdf
# soluzione in Python tramite utilizzo libreria PuLP, by Andrea Bianchini 2021
#
# Problema:
# Un lanificio produce filato di tipo standard e di tipo speciale
# utilizzando 3 diverse macchine, le cui produzioni orarie sono le seguenti:
# macchina A: 3 matasse standard e 1 speciale
# macchina B: 2 matasse standard e 2 speciali
# macchina C: 2 matasse standard e 1 speciale
# Il mercato richiede almeno 60 matasse standard e 40 di tipo speciale al giorno. I costi
# orari delle due macchine sono: 90 euro per la A, 80 euro per B, 60 euro per C.
# Scrivere un modello di programmazione lineare per determinare la produzione giornaliera
# di costo minimo. (Non occorre imporre il vincolo che le ore giornaliere non superino 24)
#


from pulp import *

a = pulp.LpVariable("a", lowBound=0)
b = pulp.LpVariable("b", lowBound=0)
c = pulp.LpVariable("c", lowBound=0)

problem = pulp.LpProblem("Un semplice problema di min", LpMinimize)

problem += 90*a + 80*b + 60*c, "The objective function"
problem += 3*a + 2*b + 2*c >= 60, "1st constraint"
problem += a + 2*b + c >= 40, "2nd constraint"
problem += a >= 0, "3rd constraint"
problem.solve()

print("Risultati della ottimizzazione:")
for variable in problem.variables():
    print(variable.name + "=" + str(variable.varValue))
print("Costo minimo netto totale: %.1f" %value(problem.objective))

Esempio:

Risultati della ottimizzazione:
a=0.0
b=10.0
c=20.0
Costo minimo netto totale: 2000.0
>>>