Algorytm Plecakowy w Pythonie

Question

Cały kod działa, ale wyniki wychodzą poprawne tylko do pewnego momentu. W tabeli P błąd widać przy i =4 a w tabeli Q dla i =5. W odpowiedzi prawidłowej występuje również: P[6][23] =80 i Q[6][23]=5 przy czym Q[6][22]=4

Implementacja kodu, dane i prawidłowe rozwiązanie zaczerpnięte z książki Sysło ,,Algorytmy".

Bardzo prosze o pomoc w znalezieniu blędu i jego wyjaśnienie

def Plecak(p,w,Waga):
    n=len(p)
    W=Waga+1
    Q=[]
    P=[]
    for i in range(0,n):
        P.append([])
        Q.append([])
        for j in range(0,W):
            P[i].append(0)
            Q[i].append(0)

    for i in range(1,n):
        for j in range(1,W):
            if j>=w[i] and P[i-1][j] <(P[i][j-w[i]]+p[i]):
                P[i][j],Q[i][j] = (P[i][j-w[i]]+p[i]),i
            else:
                P[i][j],Q[i][j] = P[i-1][j], Q[i-1][j]
    return (P,Q)

p=[0,6,4,5,6,10,2]
w=[0,6,2,3,2,3,1]
Waga=23

P,Q=Plecak(p,w,Waga)
print(P[1:len(p)])
print(Q[1:len(p)])

 

Comments

Zła kategoria

---

Nie wiem czy po roku warto to wspominać ;)

---

A rzeczywiście. Zmyliło mnie podbicie pytania przez jakiegoś użytkownika którego odpowiedź została ukryta ;d