ナップザック問題を解いてみた

背景・目的

こんにちは. プログらミング初心者です. 今回はEDPCのD問題について勉強したOUTPUTです. 内容に関して分かりずらい点や解釈に誤りが含まれていれば, ご指摘していただけますと今後の励みになります.

関連サイト

アルゴリズムとデータ構造
EDPCの問題サイト
参考YouTubeサイト

結論

各条件での最適値をテーブルデータに落として込んで値落とし込んだ値を参照しながら求めたい解を得る方法．
つまり，最小コストとなるように計算または保存したデータから参照しつつ, 最大の結果を求める方法.

内容・説明

　まずナップザック問題についてここではN種類（＝ｇ）の品から適当に選択し選んだ品の合計の重さがＷ以内の時，選んだ内訳の価値の合計が最大になるように選択すること．
　この問題のポイントは選択した内容の最終的なトータルの価値を知りたいという点である．重さは一般的に選択時の基準になる物であり，詩集的に求められる価値が解である．
ふたつの制約が異なる場所で発生している点がこの問題を難しくしている．
　またどれを選ぶという点でも選ぶか選ばないかの2^n 回の計算結果となる．計算量，制約共に工夫が必要というのがここまで内容をまとめてよくわかる．
考えとしては縦の行にw[i]の各状態での重さ，横の列で0～Wまで増やした状態での重さでの最適解を求めて，それを表を参照しながら求めるというものである．

1try

1回目に書いたコード(失敗した).　

n, W = map(int, input().split())
w = [0] * (n+1)
v = [0] * (n+1)
for i in range(1, n + 1):
    w[i], v[i] = map(int, input().split())
dp = []
dp = [[0] * (W+1) for _ in range(n + 1)]

for i in range(n + 1):
    for wi in range(W + 1):
        if wi - w[i] < 0:
            dp[i][wi] = dp[i - 1][wi]
        else:
            dp[i][wi] = max(dp[i - 1][wi], dp[i][wi - w[i]] + v[i])
print(dp[n][W])
print(dp)

出力

下記に出力をまとめます.本来一番右下の欄は17が正解ナノですがこのコードは25です.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	5	5	5	5	5	5	10	10	10	10
0	0	0	0	0	6	6	6	6	6	12	12	12	12	12	18
0	0	0	0	0	6	6	6	6	6	12	12	12	12	12	18
0	0	0	0	0	6	6	6	6	6	12	12	12	12	12	18
0	0	0	5	5	6	10	10	11	15	15	16	20	20	21	25
0	0	0	5	5	6	10	10	11	15	15	16	20	20	21	25

まず結論から言うと，これは重複して計算しているのが問題です. 具体的にコードの問題部分は

dp[i][wi] = max(dp[i - 1][wi], dp[i][wi - w[i]] + v[i])

ここで表のwiの差がw[i]が２つ以上は存在できる状態だと重複計算として求められてしまうようです．
　分析結果　-->　同じ行を参照して値を得ていたのが問題でした．つまり, 下記のようにコードを帰れば正解です

dp[i][wi] = max(dp[i - 1][wi], dp[i][wi - w[i]] + v[i])

これでいけます. 下記に最終的なコードを示します．

n, W = map(int, input().split())
w = [0] * (n+1)
v = [0] * (n+1)
for i in range(1, n + 1):
    w[i], v[i] = map(int, input().split())
dp = []
dp = [[0] * (W+1) for _ in range(n + 1)]

for i in range(n + 1):
    for wi in range(W + 1):
        if wi - w[i] < 0:
            dp[i][wi] = dp[i - 1][wi]
        else:
            dp[i][wi] = max(dp[i - 1][wi], dp[i-1][wi - w[i]] + v[i])
print(dp[n][W])

でサイトに提出した結果，

時間切れであった．とりあえず今回は時間切れで次の機械にループを時間内にクリアを目指すことにします.

今後の展望

　とりあえず時間切れのままでいいとして，今行っているテキストを周回する事を専念します．これはモチベ対策で、D問題は気が向いたらやります。
　けどその前に大学のテスト勉強と課題のレポート提出...頑張ります．