離散ナップザック動的プログラミングPython3

Question

これは私の動的プログラミングを扱う最初の課題であり、私はそれがかなり難しいと思っています。

問題：[0]、...、重量[N重量重みの

容量Wのナップザックを考えると、nは金の延べ棒[ - 1]、リュックサックに収まることができる金の延べ棒の最大数を見つけます繰り返しなし。

入力： 行1：（容量ナップザック（W））（NUM金バー（N）） ライン2：Nゴールドバー（重量）

出力の重み：最大量（金バーの）

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

私が間違っているつもりです任意のアイデア：それは

私のコードW容量のナップザックに収まることができますか？私がmax_valsの終了を観察すると、max_valsが増えるにつれて、各入れ子リスト内のより小さい値（i-1）だけが置き換えられることがわかります。言い換えれば、私が反復を続けると、max_vals [i - 1] [j]の値で置き換えられる数は少なくなります。幾分恥ずかしいことに、私はこれをほぼ一週間働いており、それを理解することはできません。 This videoは、クラス講演ビデオとは別に、私の主な参照点です。動的プログラミングはかなり大きな課題であることが証明されています。

Answer 1

簡単に修正できます。私はそれを逃したと信じられない。ちょうどelseステートメントを台無しにしていた。特別な必要があった。

 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]