97 lines
2.3 KiB
Python
97 lines
2.3 KiB
Python
# Kod napisany przez: Jakub Markil
|
|
|
|
from item import *
|
|
from funkcje import ograniczenie
|
|
|
|
liczba_itemow = 20
|
|
dost = []
|
|
for i in range(liczba_itemow):
|
|
item = Item()
|
|
ratio = item.ratio
|
|
dost.append((ratio, item))
|
|
|
|
r = [el[0] for el in dost]
|
|
r.sort(reverse=True)
|
|
dostepne_items = []
|
|
for i in r:
|
|
for j in dost:
|
|
if i == j[0]:
|
|
dostepne_items.append(j[1])
|
|
break
|
|
|
|
|
|
for x in dostepne_items:
|
|
print(x.waga, x.wartosc)
|
|
|
|
cap = 4 * liczba_itemow / 2 # te liczby tutaj są raczej przypadkowe i można je zmieniać, algorytm dalej powinien działać
|
|
alfa = liczba_itemow * 5
|
|
|
|
|
|
def knapsack(dostepne, cap, mode):
|
|
|
|
def rekurencja(i, waga, val, items):
|
|
nonlocal max_val, plecak, actions
|
|
|
|
actions += 1
|
|
if i >= len(dostepne):
|
|
if val > max_val:
|
|
max_val = val
|
|
plecak = items
|
|
return
|
|
|
|
if mode in [1, 2] and waga >= cap: # alfa cięcie part 1
|
|
return
|
|
|
|
if mode in [2] and max_val >= val + ograniczenie(dostepne[i:], cap-waga): # beta cięcie
|
|
return
|
|
|
|
if waga + dostepne[i].waga <= cap: # alfa cięcie part 2
|
|
temp = items[:]
|
|
temp.append(dostepne[i])
|
|
rekurencja(i+1, waga + dostepne[i].waga, val + dostepne[i].wartosc, temp)
|
|
|
|
rekurencja(i+1, waga, val, items[:])
|
|
|
|
max_val = float("-inf")
|
|
plecak = []
|
|
actions = 0
|
|
rekurencja(0, 0, 0, [])
|
|
return plecak, actions
|
|
|
|
|
|
final0, actions0 = knapsack(dostepne_items, cap, 0)
|
|
final1, actions1 = knapsack(dostepne_items, cap, 1)
|
|
final2, actions2 = knapsack(dostepne_items, cap, 2)
|
|
|
|
total_w0 = 0
|
|
best_val0 = 0
|
|
total_w1 = 0
|
|
best_val1 = 0
|
|
total_w2 = 0
|
|
best_val2 = 0
|
|
for item in final0:
|
|
total_w0 += item.waga
|
|
best_val0 += item.wartosc
|
|
|
|
for item in final1:
|
|
total_w1 += item.waga
|
|
best_val1 += item.wartosc
|
|
|
|
for item in final2:
|
|
total_w2 += item.waga
|
|
best_val2 += item.wartosc
|
|
|
|
print("----------\n" + f'wartości plecaka: {best_val0} - {best_val1} - {best_val2}')
|
|
print(f"waga plecaka: {total_w0}/{int(cap)} - {total_w1}/{int(cap)} - {total_w2}/{int(cap)}")
|
|
|
|
binar = ''
|
|
for item in dostepne_items:
|
|
binar += "1" if item in final0 else "0"
|
|
|
|
print(binar)
|
|
|
|
print("---------------")
|
|
print(f"Wierzchołki na surowo: {actions0}")
|
|
print(f"Wierzchołki z alfa cięciem: {actions1}")
|
|
print(f"Wierzchołki z alfabeta cięciem: {actions2}")
|