Educational DP Contest
Educational DP Contest - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
問題
D - Knapsack 1
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
方針
\(N\)が小さく、\(W\)が大きい。また\(v_i\)も大きいので、計算量が\(O(NW)\)となるようにする。蟻本にあるように、\((N+1)(W+1)\)の配列を作る。二次元配列以上だとnumpyが便利なので、PyPy3は使えない。
解答
#another
#atcoder template
def main():
import sys
input = sys.stdin.readline
#文字列入力の時は上記はerrorとなる。
#ここにコード
n, W = map(int, input().split())
import numpy as np
dp = np.zeros((n+1, W+1), np.int64)
for i in range(n):
w, v = map(int, input().split())
np.maximum(dp[i, w:], dp[i, :-w]+v, out = dp[i+1, w:])
dp[i+1, :w] = dp[i, :w]
print(dp[-1, -1])
#N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
main()提出結果
Submission #31741688 - Educational DP Contest
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
補足
DP tableが更新される様子を入力例3で確認してみる。最初に作られるのは以下のようなテーブル。
array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])これは行が\(6+1\)、列が\(15+1\)の行列と考えると簡便である。for loopを回すと
array([[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, 5, 5, 5, 5],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])ここでは\(1\)行目（Pythonのindexは\(0\)から始まることに注意）
array([[ 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, 5, 5, 5, 5],
[ 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 6, 11, 11, 11, 11, 11],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])array([[ 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, 5, 5, 5, 5],
[ 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 6, 11, 11, 11, 11, 11],
[ 0, 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 11, 11, 11, 11, 11],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])array([[ 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, 5, 5, 5, 5],
[ 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 6, 11, 11, 11, 11, 11],
[ 0, 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 11, 11, 11, 11, 11],
[ 0, 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 11, 12, 12, 12, 12],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])array([[ 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, 5, 5, 5, 5],
[ 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 6, 11, 11, 11, 11, 11],
[ 0, 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 11, 11, 11, 11, 11],
[ 0, 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 11, 12, 12, 12, 12],
[ 0, 0, 0, 5, 5, 5, 6, 6, 6, 11, 11, 11, 12, 12, 16, 17],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])array([[ 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, 5, 5, 5, 5],
[ 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 6, 11, 11, 11, 11, 11],
[ 0, 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 11, 11, 11, 11, 11],
[ 0, 0, 0, 0, 0, 0, 6, 6, 6, 6, 6, 11, 12, 12, 12, 12],
[ 0, 0, 0, 5, 5, 5, 6, 6, 6, 11, 11, 11, 12, 12, 16, 17],
[ 0, 0, 0, 0, 0, 0, 0, 6, 6, 11, 11, 11, 12, 12, 16, 17]])のように更新されていく。よりわかりやすく、枠で囲むと以下のようになる。
このときは、\(w_0= 6\)なので、黄色の枠がindex\(0\)からindex\(-7(-6-1)\)まであって、緑の枠がindex\(6\)から最後まである。黄色の配列に\(v_0 = 5\)を足した\([5, 5, 5, 5, 5, 5, 5, 5, 5, 5]\)と緑の配列\([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\)の大きい方を取った配列は\([5, 5, 5, 5, 5, 5, 5, 5, 5, 5]\)になるので、赤い部分は\([5, 5, 5, 5, 5, 5, 5, 5, 5, 5]\)になる。
このときは、\(w_1= 5\)なので、黄色の枠がindex\(0\)からindex\(-6(-5-1)\)まであって、緑の枠がindex\(5\)から最後まである。黄色の配列に\(v_1 = 6\)を足した\([6, 6, 6, 6, 6, 6, 11, 11, 11, 11, 11]\)と緑の配列\([0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]\)の大きい方を取った配列は\([6, 6, 6, 6, 6, 6, 11, 11, 11, 11, 11]\)になるので、赤い部分は\([6, 6, 6, 6, 6, 6, 11, 11, 11, 11, 11]\)になる。後は以下同様であるので、画像だけ載せる。
配列の一番最後が、求める値\(17\)になっている。
コメント