[Python3][リスト]リストの初期化方法を変えると、任意の要素へ代入した際にすべての行の要素が変更されてしまう。

前提・実現したいこと

リストの初期化の方法が異なると、同じコードを実行しても異なる出力が得られるのですが、挙動が異なる理由がわかりません。
一見同じように機能するように思える二つの初期化方法で、なぜ一方は不適当な動作をするのか、教えていただけないでしょうか？

問題：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp
（秋葉ほか『プログラミングコンテストチャレンジブック』 p.52）

発生している問題・エラーメッセージ

次のようにdpを初期化すると、計算時、各行の列成分が同一になります。

初期化コードと問題ある出力

Python3
1dp = [[0] * (W + 1)] * N + [[0] * (W + 1)]    #正しく出力しない
2[[0, 2, 5, 8, 10, 13],
3 [0, 2, 5, 8, 10, 13],
4 [0, 2, 5, 8, 10, 13],
5 [0, 2, 5, 8, 10, 13],
6 [0, 0, 0, 0, 0, 0]]
7#一番下の行を除いて、すべての行で列成分が同じになる

正しいdpの出力と対応するコード（入力例 1）

dp = [[0] * (W + 1) for i in range(N + 1)]     #正しく出力する

[[0, 2, 5, 8, 10, 13],
 [0, 2, 5, 8, 10, 13],
 [0, 2, 2, 8, 10, 10],
 [0, 0, 0, 8, 8, 8],
 [0, 0, 0, 0, 0, 0]]

該当のソースコード

Python3
1import pprint
2
3N, W = map(int, input().split())
4w = [0] * (N + 1)
5v = [0] * (N + 1)
6for _ in range(N):
7    v[_], w[_] = map(int, input().split())
8
9dp = [[0] * (W + 1)] * (N + 1)
10
11
12dp = [[0] * (W + 1)] * N + [[0] * (W + 1)]
13#dp = [[0] * (W + 1) for i in range(N + 1)]
14dp[N][W] = 0
15
16for i in range(N - 1, -1, -1):
17    for j in range(W + 1):
18        # 重量オーバー
19        if j < w[i]:
20            dp[i][j] = dp[i + 1][j]
21        # jよりw[i]が小さい場合：　入れないとき・入れるときの価値を比較し最大値
22        else:
23            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i])
24
25
26pprint.pprint(dp)
27

入力例1

上記の出力は次の入力に対するものです。
4 5
4 2
5 2
2 1
8 3

補足情報（FW/ツールのバージョンなど）

Python3.7 anacondaを使用
01ナップザック問題を動的計画法で解くプログラムを組んでいます。ここでは配列dp[i][j]を、「i番目以降の品物から重さの総和がj以下になるように選んだ商品の価値の総和」としています。そのため、dp[i][j]の数値は各行でそれぞれ異なっているはずです。

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

回答2件

ベストアンサー

１つめは、[0,0,・・,0]を*で複製しているので、同じオブジェクトを並べているだけす。
dp[0]とdp[1]は同じオブジェクトなので、dp[0]の中身を書き換えると。dp[1}もそれを参照しているので同じものが表示されます。

Python
1A=[0]
2B=A
3A[0]=2
4print(B[0])

で、2が表示されるのと同じ理由です。

２つめは、forの繰り返しごとに別のオブジェクトを生成しています。

Python
1A=[0]
2B=[0]
3A[0]=2
4print(B[0])

これは、0ですね。

投稿2020/04/10 12:59

otn

総合スコア84684

noyan

2020/04/10 13:15

同一のオブジェクトを参照しているので、そのオブジェクトを参照している各行が同じになるんですね。ありがとうございます！ A= [0] * 3 とした場合には、複製ではなくそれぞれ別のオブジェクトが生成されますが、表題の件とこのケースの違いはどこにうまれるのでしょうか？

otn

2020/04/10 14:13

それは、 A=[[0]]*3 => [[0], [0], [0]] A[0][0]=2 => [[2], [2], [2]] と A=[[0]]*3 => [[0], [0], [0]] A[0]=[2] => [[2], [0], [0]] の違いです。後者はオブジェクトの中身を書き換えるのじゃなくて、オブジェクトを別のオブジェクトで差し替えているので、差し替えなかった他のオブジェクトは無関係です。（「差し替え」という表現は今作ったので、一般的でないかもしれません） A=[0,0,0] A[:]=[1,2,3] と、 A=[0,0,0] A=[1,2,3] の違いは判りますか？前者はリストオブジェクトの中身の書き換えで、後者は別のリストオブジェクトとの差し替えです。 A= [0] * 3 の場合でも、A[0]の 0 という数値オブジェクトの中身を書き換えられればリストの中身の書き換えと同じような結果にできるはずですが、数値オブジェクトの中身を書き換えることはできません。できるのは別の数値と差し替えることだけです。

noyan

2020/04/11 04:57

ご返答ありがとうございます。二つの例で動作が異なるのは、それぞれ、参照先を差し替える、オブジェクトのIDは同一のまま中身を入れ替えるという別のことを行っているからなんですね。丁寧な解説、とてもたすかりました！

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

otn様の回答に補足するかたちで回答します。

pythonのlistに*した際の挙動については以下のqiita記事が詳しいので、ご覧いただければと思います。
リストを*したときの挙動

リストを*した場合、参照情報がコピーされます。指しているものがコピーされるわけではありません。

Python
1hoge = [0]*2
2print(hoge,id(hoge[0]),id(hoge[1]))
3
4hoge[0] += 1
5print(hoge,id(hoge[0]),id(hoge[1]))
6
7>[0, 0] 10914464 10914464
8>[1, 0] 10914496 10914464

上の例では0というオブジェクトが複製されているだけで、ある要素への変更は別の要素へ影響を及ぼしません。

Python
1hoge = [[0]]*2
2print(hoge,id(hoge[0]),id(hoge[1]))
3
4hoge[0][0] += 1
5print(hoge,id(hoge[0]),id(hoge[1]))
6
7>[[0], [0]] 140162616131080 140162616131080
8>[[1], [1]] 140162616131080 140162616131080

下の例では[0]という配列を*しているため、参照がコピーされています。
また、この例ではidが140162616131080である配列に対してその先頭要素を1加算する処理をしています。
その場合、idが140162616131080である配列すべてが影響を受けます。

Python
1hoge = [[0]]*2
2print(hoge,id(hoge[0]),id(hoge[1]))
3
4hoge[0] = [1]
5print(hoge,id(hoge[0]),id(hoge[1]))
6
7>[[0], [0]] 140162605017608 140162605017608
8>[[1], [0]] 140162615797704 140162605017608