D - Knapsack 1, E - Knapsack 2, A - コンテスト

##[D - Knapsack 1](https://atcoder.jp/contests/dp/tasks/dp_d)

O(N*W)
メモ化再帰を使用しました。

```python:python
import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

N = 0
WS = [0]
VS = [0]
dp = []

def dfs(n, Weight)->int:
    global dp
    if n==0:
        dp[n][Weight] = 0
        return dp[n][Weight]
    if dp[n][Weight]>=0:
        return dp[n][Weight]
    elif Weight - WS[n] < 0:
        dp[n][Weight] = max(dp[n][Weight], dfs(n-1, Weight))
    else:
        dp[n][Weight] = max(dfs(n-1, Weight), dfs(n-1, Weight-WS[n]) + VS[n])

    return dp[n][Weight]


# main
def main():
    sys.setrecursionlimit(1000000)

    global N, WS, VS
    N, W = list(map(int, input().split()))

    for i in range(0, N):
        w, v = list(map(int, input().split()))
        WS.append(w)
        VS.append(v)

    for _ in range(0, N+1):
        row = [-1] * (W+1)
        dp.append(row)

    res = dfs(N, W)
    print(res)
            
# エントリポイント
if __name__ == '__main__':
    main()
```

O(N*W)
個数＊重さ基準で２次元配列をグラフ化した時のコード。

```python:python
import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():

    N, W = list(map(int, input().split()))
    WS = [0]
    VS = [0]
    dp = []

    for i in range(0, N):
        w, v = list(map(int, input().split()))
        WS.append(w)
        VS.append(v)

    for _ in range(0, N+1):
        row = [0] * (W+1)
        dp.append(row)

    dp[0][0] = 0
    for i in range(0, N+1):
        for sum_w in range(0, W+1):
            if sum_w - WS[i] >= 0:
                dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w-WS[i]] + VS[i])
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

    print(dp[N][W])
            
# エントリポイント
if __name__ == '__main__':
    main()
```

##[E - Knapsack 2](https://atcoder.jp/contests/dp/tasks/dp_e)

[D - Knapsack 1](https://atcoder.jp/contests/dp/tasks/dp_d)のWとVの関係を逆にした問題です。

O(N*W)
個数＊価値基準で２次元配列をグラフ化した時のコード。

```python:python
import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    N, W = list(map(int, input().split()))
    WS = [0]
    VS = [0]
    dp = []

    for i in range(0, N):
        w, v = list(map(int, input().split()))
        WS.append(w)
        VS.append(v)

    for _ in range(0, N+1):
        row = [1000000000+7] * (N*1000+1)
        dp.append(row)

    dp[0][0] = 0
    MAX_V = sum(VS)
    for i in range(1, N+1):
        for sum_v in range(0, MAX_V+1):
            if sum_v - VS[i] >= 0:
                dp[i][sum_v] = min(dp[i][sum_v], dp[i-1][sum_v - VS[i]] + WS[i])
            dp[i][sum_v] = min(dp[i][sum_v], dp[i-1][sum_v])
            
    res = 0
    for sum_v in range(0, MAX_V+1):   
        if dp[N][sum_v] <= W:
            res = max(res, sum_v)

    print(res)
            
# エントリポイント
if __name__ == '__main__':
    main()
```

##[A - コンテスト](https://atcoder.jp/contests/tdpc/tasks/tdpc_contest)

O(N*P)

```python:python
import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    N = int(input())
    P = [0] + list(map(int, input().split()))
    dp = []

    for _ in range(0, N+1):
        row = [False] * (sum(P)+1)
        dp.append(row)

    dp[0][0] = True
    for i in range(1, N+1):
        for sum_v in range(0, sum(P)+1):
            if sum_v - P[i] >= 0 and dp[i-1][sum_v-P[i]]:
                dp[i][sum_v] = dp[i-1][sum_v-P[i]]
            else:
                dp[i][sum_v] = dp[i-1][sum_v]

    print(sum(dp[N]))
            
# エントリポイント
if __name__ == '__main__':
    main()
```