[AtCoder][DP][Educational DP Contest]D-Knapsack 1

Table of Contents

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.

問題

D - Knapsack 1

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

方針

\(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.

補足

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]\)になる。後は以下同様であるので、画像だけ載せる。