Python Numpyを用いてナップザック問題をDPで解く（Atcoder例題）

Pythonでナップザック問題どうやって解くんだっけ？というときに参照するページです。 Atcoderなどリアルタイム性が必要なときはC++かPyPyで実装すること（戒め）

ナップザック問題説明

省略。Wikiとかを見てください。アルゴリズムの理解は以下の記事がわかりやすいと思います。

qiita.com

Atcoder問題例

2020年6月13日に行われた東京海上主催のAtcoderのD問題のために書き起こしました。

atcoder.jp

なお，私は Pythonでの高速化に失敗しTLEを連発し敗北しました。

解決策として Numpyを使いながらjitなどで高速化するか，Numpyを廃してPyPyで実装するか，C++に乗り換えるかしましょう。

PythonのDPコード Numpy有

入力は4つ，今回は入力は全て正の整数とします。唯一価値だけは非整数でも大丈夫です。

• N：品物の数
• W：重さの制限
• weight：価値のリスト
• weight：重さのリスト

def solveDP(N, W, value, weight):
    dp = np.zeros((N+1, W+1))
    
    for i in range(N):
        for w in range(W+1):
            if w >= weight[i]:
                dp[i + 1, w] = max(dp[i, w - weight[i]] + value[i], dp[i, w])
            else:
                dp[i + 1, w] = dp[i, w]
    
    return dp[N , W]

PythonのDPコード Numpyなし

以下のサイトから拝借しました。

Pythonで解くナップサック問題【動的計画法（DP）入門】 - nashidos’s diary

やってることは全く同じです。ただ，こちらはNumpyを使わないのでPyPyでも使えるという利点があります。 Atcoderではこちらを使いましょう（涙）。

def solveDP(N,W,v,w):
    dp = [[0]*(W+1) for j in range(N+1)] # DPテーブルの作成

    for i in range(N):
        for j in range(W+1):
            if j < w[i]: # 選ばない時
                dp[i+1][j] = dp[i][j]
            else: # 選ぶ時
                dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])
                
    return dp[N][W]

ちなみに6/13に行われたこのコンテスト，Python勢には辛かったらしく，PythonでC問題を通したのが3人，Dが1人でした。

Pythonはプレミ。