Ayrık Sırt Çantası Dinamik Programlama Python3

Question

Bu, Dinamik Programlama ile ilgili ilk görevimdir ve bunu oldukça zor buluyorum.

Sorun:

[[0], ..., ağırlıkça [n ağırlık olarak ağırlıklarının kapasitesi W ve n altın bar bir sırt çantası Verilen - 1], sırt çantası içine sığabilecek altın çubukların sayısını bulmak tekrarlama olmadan

girişi: hat 1: (kapasite sırt çantası (W)) (num altın çubukları (n)) hat 2: n-altın bar (ağırlıkça)

çıkış ağırlıkları: maksimum ağırlık (altın çubukların) o

Benim kod W kapasite çantasında sığabilecek:

import sys 

def optimal_weight(W, wt): 
    """Find max weight that can fit in knapsack size W.""" 
    # Create n nested arrays of 0 * (W + 1) 
    max_vals = [[0] * (W + 1) for x in range(len(wt))] 
    # Set max_vals[0] to wt[0] if wt[0] <= j 
    max_vals[0] = [wt[0] if wt[0] <= j else 0 for j in range(W + 1)] 
    for i in range(1, len(wt)): 
     for j in range(1, W + 1): 
      value = max_vals[i - 1][j] # previous i @ same j 
      if wt[i] <= j: 
       val = (max_vals[i - 1][j - wt[i]]) + wt[i] 
       if value < val: 
        value = val 
        max_vals[i][j] = value 
       else: 
        max_vals[i][j] = value 

    return max_vals[-1][-1] 

if __name__ == '__main__': 
    input = sys.stdin.read() 
    W, n, *wt = list(map(int, input.split())) 
    print(optimal_weight(W, wt)) 

herhangi bir fikir yanlış nereye gidiyorum? Sonuncu max_val'larımı gözlemlediğimde, max_vals'ın, arttığım gibi, her iç içe geçmiş listede yalnızca giderek daha küçük olan değerlerin (i - 1) yerini aldığını görüyorum. Diğer bir deyişle, yinelemeye devam ederken, 0'dan azı, max_vals [i - 1] [j] değeriyle değiştirilir. Biraz utanç verici, neredeyse bir hafta boyunca bunun üzerinde çalışıyorum ve bunu anlayamıyorum. Sınıf ders videosu dışında This video, ana referans noktam oldu. Dinamik programlama oldukça büyük bir meydan okuma olduğunu kanıtlıyor.

Answer 1

Çok kolay düzeltme. Onu özlediğime inanamıyorum. Sadece başka ifadelerle uğraşıyordum. Ekstra gerekiyordu.

 if value < val: 
       value = val 
       max_vals[i][j] = value 
      else: 
       max_vals[i][j] = value # set to [i - 1][j] 
     else: 
      max_vals[i][j] = value # set to [i - 1][j]