01ナップザック問題で出力がなぜか変化する

###書いたコード
01ナップザック問題の１解法です。AtCoderのABC032Dを解いているときに遭遇した謎です。

python
1import numpy as np
2N,W = map(int,input().split())
3v_list = []
4w_list = []
5for n in range(N):
6    v,w = map(int,input().split())
7    v_list.append(v)
8    w_list.append(w)
9
10#dp = [[0]*(W+1)]*(N+1)
11dp = np.zeros((N+1,W+1))
12
13for i in range(N-1,-1,-1):
14    for j in range(W+1):
15        if w_list[i] > j:
16            dp[i][j] = dp[i+1][j]
17        else:
18            dp[i][j] = max(dp[i+1][j],dp[i+1][j-w_list[i]]+v_list[i])
19print(int(dp[0][W]))

python
1import numpy as np
2N,W = map(int,input().split())
3v_list = []
4w_list = []
5for n in range(N):
6    v,w = map(int,input().split())
7    v_list.append(v)
8    w_list.append(w)
9
10dp = [[0]*(W+1)]*(N+1)
11#dp = np.zeros((N+1,W+1))
12
13for i in range(N-1,-1,-1):
14    for j in range(W+1):
15        if w_list[i] > j:
16            dp[i][j] = dp[i+1][j]
17        else:
18            dp[i][j] = max(dp[i+1][j],dp[i+1][j-w_list[i]]+v_list[i])
19print(int(dp[0][W]))

標準入力は以下

10 2921
981421680 325
515936168 845
17309336 371
788067075 112
104855562 96
494541604 960
32007355 161
772339969 581
55112800 248
98577050 22

変えたのは中盤のリストdpの定義だけです。同じリストを作ったつもりだったのですが、上と下で出力が変化します。原因はなんでしょうか？ちなみに正しい出力は3657162058です。

行動規範の内容に同意します

回答1件

ベストアンサー

Python

dp = [[0](W+1)](N+1)
#dp = np.zeros((N+1,W+1))

よくハマる罠です。

Python
1>>> lst = [[0] * 10] * 10
2>>>
3>>> print(*lst, sep='\n')
4[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
5[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
6[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
7[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
8[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
9[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
10[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
11[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
12[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
13[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
14>>>
15>>> lst[0][0] = 1
16>>>
17>>> print(*lst, sep='\n')
18[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
19[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
20[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
21[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
22[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
23[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
24[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
25[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
26[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
27[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]