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)])