Python Numpyを用いてナップザック問題をDPで解く(Atcoder例題)
Pythonでナップザック問題どうやって解くんだっけ?というときに参照するページです。 Atcoderなどリアルタイム性が必要なときはC++かPyPyで実装すること(戒め)
ナップザック問題説明
省略。Wikiとかを見てください。アルゴリズムの理解は以下の記事がわかりやすいと思います。
Atcoder問題例
2020年6月13日に行われた東京海上主催のAtcoderのD問題のために書き起こしました。
なお,私は 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はプレミ。