from timeit import default_timer as timer

# Konačno rješenje pomoću dynamic programming-a
# Program za 0-1 knapsack problem
# Isto kao i prethodni program vraća maksimalnu vrijednost
# koja se može staviti u knapsack kapaciteta T
def knapSack(T, tp, val, n):
    K = [[0 for x in range(T + 1)] for x in range(n + 1)]

    # Popunjava tablicu bottom-up redoslijedom
    for i in range(n + 1):
        for j in range(T + 1):
            if i == 0 or j == 0:
                K[i][j] = 0
            elif tp[i - 1] <= j:
                K[i][j] = max(val[i - 1] + K[i - 1][j - tp[i - 1]], K[i - 1][j])
            else:
                K[i][j] = K[i - 1][j]

    return K[n][T]


# kraj knapSack funkcije


# Testiranje gornje funkcije
# val - niz vrijednosti predmeta
# tp - težina predmeta
# T - maksimalna težina, odnosno kapacitet knapsack-a
# n - količina predmeta
"""val = [60, 100, 120, 150, 210, 250, 300, 310, 320, 340]
tp = [10, 20, 30, 40, 40, 50, 55, 60, 70, 90]
T = 500
n = len(val)

start = timer()
print('Maksimalna vrijednost koju mozes ukrasti je: ')
print(knapSack(T, tp, val, n))

end = timer()
print(end - start)"""


val = []
tp = []

print('Vi ste lopov te ste provalili u kucu. Cilj vam je ukrasti sto vise, no limitira vas velicina vaseg ruksaka, a ne vrijedi svaki predmet isto.')
print('Prvo sto trebate napraviti je unijeti kapacitet vaseg ruksaka.')

T = int(input('Unesi kapacitet knapsacka: '))

print('S obzirom da si limitiran velicinom ruksaka, postoji mogucnost da neces moci ukrasti sve predmete, ')
print('stoga ti je cilj ukrasti sto vecu vrijednost u predmetima, a da pritom oni stanu u tvoj ruksak.')
print('Sada kada znamo koliko da je kapacitet vaseg ruksaka %d, unesi u program vrijednosti i tezine predmeta koje mozes ukrast.'%T)

#unos vrijednosti i tezina predmeta
#unos se prekida kada se unese 0 kao vrijednost i tezina predmeta
i=0
while 1:
    i += 1
    value = int(input('Unesi vrijednost predmeta %d.: '%i))
    weight = int(input('Unesi tezinu predmeta %d.: '%i))
    if value == 0 and weight == 0:
         break
    val.append(value)
    tp.append(weight)

n = len(val)

#ispis vrijednosti predmeta
print(val)

#ispis tezina predmeta
print(tp)


start = timer()
print('Maksimalna vrijednost koju mozes ukrasti je: ')
print(knapSack(T, tp, val, n))

end = timer()
print(end - start)