Problem:


Score : 100 points

Problem Statement

There are N items, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.

Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.

Sample Input 2

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

5000000000

The answer may not fit into a 32-bit integer type.

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


N, W = map(int, input().split())
w_v = [[int(_) for _ in input().split()] for _ in range(N)]
dp = np.zeros([N, W+1], dtype=int)
dp[0][w_v[0][0]:] = w_v[0][1]

for i in range(1, N):
    dp[i][:w_v[i][0]] = dp[i-1][:w_v[i][0]]
    for w in range(w_v[i][0], W+1):
        dp[i][w] = max(dp[i-1][w], dp[i-1][w - w_v[i][0]] + w_v[i][1])

print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


N, W = map(int, input().split())
w_v = [[int(_) for _ in input().split()] for _ in range(N)]
dp = np.zeros([N, W+1], dtype=int)
dp[0][w_v[0][0]:] = w_v[0][1]

for i in range(1, N):
    dp[i][:w_v[i][0]] = dp[i-1][:w_v[i][0]]
    for w in range(w_v[i][0], W+1):
        dp[i][w] = max(dp[i-1][w], dp[i-1][w - w_v[i][0]] + w_v[i][1])

print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


N, W = map(int, input().split())
w_v = [[int(_) for _ in input().split()] for _ in range(N)]
dp = np.zeros([N, W+1], dtype=int)
dp[0][w_v[0][0]:] = w_v[0][1]

for i in range(1, N):
    for w in range(W+1):
        dp[i][w] = (dp[i-1][w] if w - w_v[i][0] < 0 else max(dp[i-1][w], dp[i-1][w - w_v[i][0]] + w_v[i][1]))

 
print(dp[N-1][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


N, W = map(int, input().split())
w_v = [[int(_) for _ in input().split()] for _ in range(N)]
dp = np.zeros([N, W+1], dtype=int)
dp[0][w_v[0][0]:] = w_v[0][1]

for i in range(1, N):
    for w in range(W+1):
        if w - w_v[i][0] < 0:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w - w_v[i][0]] + w_v[i][1])
 
print(dp[N-1][W])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N, W = map(int, input().split())
w_v = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[0] * (W+1) for _ in range(N)]

for i in range(w_v[0][0], W+1):
    dp[0][i] = w_v[0][1]
    
for i in range(1, N):
    for w in range(W+1):
        if w - w_v[i][0] < 0:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w - w_v[i][0]] + w_v[i][1])

print(dp[N-1][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = list(map(int, input().split()))

L = [[0 for i in range(W + 1)] for j in range(N + 1)]

for i in range(N):
    w, v = list(map(int, input().split()))
    for j in range(W + 1):
        if j < w:
            L[i + 1][j] = L[i][j]
        else:
            L[i + 1][j] = max(L[i][j], L[i][j - w] + v)

print(L[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
N, W = list(map(int, input().split()))

L = [[-float("inf") for i in range(W + 1)] for j in range(N + 1)]
L[0][0] = 0

for i in range(N):
    w, v = list(map(int, input().split()))
    for j in range(W + 1):
        if L[i][j] != -float("inf"):
            if L[i + 1][j] < L[i][j]:
                L[i + 1][j] = L[i][j]
            if j + w <= W:
                if L[i + 1][j + w] < L[i][j] + v:
                    L[i + 1][j + w] = L[i][j] + v

print(max(L[N]))

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
t = [tuple(map(int, input().split())) for _ in range(n)]

dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j >= t[i][0]:
            dp[i+1][j] = max(dp[i][j-t[i][0]] + t[i][1], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N, W = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for j in range(N)]

def ans(N, W, wv):
    d = [[0] * (W+1) for i in range(N+1)]

    for i in range(N):
        for j in range(W+1):
            if wv[i][0] > j:
                d[i+1][j] = d[i][j]
            else:
                d[i + 1][j] = max(d[i][j], d[i][j-wv[i][0]] + wv[i][1])
    return d[N][W]

print(ans(N, W, wv))

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
ans=[0]*(w+1)
for i in range(n):
    e,v=map(int,input().split())
    for j in range(w,-1,-1):
        if j+e<=w:
            ans[j+e]=max(ans[j]+v,ans[j+e])
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, W):
    dp = [-1] * (W + 1)
    dp[0] = 0
    for i in range(n):
        wi, vi = map(int, input().split())
        dp_ = list(dp)
        for w in range(W + 1):
            if dp[w] >= 0:
                w_ = w + wi
                v_ = dp[w] + vi
                if w_ <= W and dp[w_] < v_:
                    dp_[w_] = v_
        dp = dp_
    return(max(dp))

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wv, W):
    dp = [-1] * (W + 1)
    dp[0] = 0
    for wi, vi in wv:
        dp_ = list(dp)
        for w in range(W + 1):
            if dp[w] >= 0:
                w_ = w + wi
                v_ = dp[w] + vi
                if w_ <= W and dp[w_] < v_:
                    dp_[w_] = v_
        dp = dp_
    return(max(dp))

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5
wv = [[int(x) for x in input().split()] for _ in range(n)]

print(f(n, wv, w))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

def f(n, wv, W):
    dp = [0] * (W + 1)
    for wi, vi in wv:
        for w in range(W, wi - 1, -1):
            dp[w] = max(dp[w], dp[w - wi] + vi)
    return(dp[-1])

n, w = map(int, input().split()) # 1 <= n <= 100, 1 <= w <= 10^5
wv = [[int(x) for x in input().split()] for _ in range(n)]

print(f(n, wv, w))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, wv, W):
    dp = [0] * (W + 1)
    for wi, vi in wv:
        for w in range(W, wi - 1, -1):
            dp[w] = max(dp[w], dp[w - wi] + vi)
    return(dp[-1])

n, w = map(int, input().split()) # 1 <= n <= 100, 1 <= w <= 10^5
wv = [[int(x) for x in input().split()] for _ in range(n)]

print(f(n, wv, w))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, W):
    dp = [0] * (W + 1)
    for i in range(n):
        wi, vi = map(int, input().rstrip().split())
        for w in range(W, wi - 1, -1):
            dp[w] = max(dp[w], dp[w - wi] + vi)
    return(dp[-1])

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, W):
    dp = [0] * (W + 1)
    wv = [list(map(int, input().rstrip().split())) for _ in range(n)]
    for wi, vi in wv:
        for w in range(W, wi - 1, -1):
            dp[w] = max(dp[w], dp[w - wi] + vi)
    return(dp[-1])

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    dp = [-1] * (wlimit + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        wi, vi = map(int, input().rstrip().split())
        dp_ = list(dp)
        for w in range(wlimit + 1):
            if dp[w] >= 0:
                w_ = w + wi
                v_ = dp[w] + vi
                if w_ <= wlimit and dp[w_] < v_:
                    dp_[w_] = v_
        dp = dp_
    return(max(dp))

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    dp = [0] * (wlimit + 1)
    wv = [list(map(int, input().rstrip().split())) for _ in range(n)]
    for wi, vi in wv:
        dp_ = list(dp)
        for w in range(wlimit + 1):
            v_ = dp[w] if w - wi < 0 else dp[w - wi] + vi
            dp_[w] = max(dp[w], v_)
        dp = dp_
    return(dp[-1])

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wv, wlimit):
    dp = [[0] * (wlimit + 1) for _ in range(n + 1)]
    for i, (wi, vi) in enumerate(wv):
        for w in range(wlimit + 1):
            w_ = w - wi
            v_ = dp[i][w] if w_ < 0 else dp[i][w_] + vi
            dp[i + 1][w] = max(dp[i][w], v_)
    return(dp[-1][-1])

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5
wv = [list(map(int, input().rstrip().split())) for _ in range(n)]

print(f(n, wv, w))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    dp = [[0] * (wlimit + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = map(int, input().rstrip().split())
        for w in range(wlimit + 1):
            w_ = w - wi
            v_ = dp[i - 1][w] if w_ < 0 else dp[i - 1][w_] + vi
            dp[i][w] = max(dp[i - 1][w], v_)
    return(dp[i][-1])

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    dp = [[-1] * (wlimit + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for i in range(1, n + 1):
        wi, vi = map(int, input().rstrip().split())
        for w in range(wlimit + 1):
            if dp[i - 1][w] >= 0:
                w_ = w + wi
                v_ = dp[i - 1][w] + vi
                if w_ <= wlimit:
                    if dp[i - 1][w_] < v_:
                        dp[i][w_] = v_
                if dp[i][w] < dp[i - 1][w]:
                    dp[i][w] = dp[i - 1][w]
    return(max(dp[i]))

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    # dp[i][w]
    #   i番目の品物までで w を超えないように選んだ最大価値
    dp = { 0: 0 }   # { <sum weight>: <sum value> }
    for i in range(1, n + 1):
        dp_ = {}
        wi, vi = map(int, input().rstrip().split())
        for w, v in dp.items():
            w_ = w + wi
            v_ = v + vi
            if w_ <= wlimit and (w_ not in dp or dp[w_] < v_):
                dp_[w_] = v_
        dp.update(dp_)
    return(max(dp.values()))

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))

Submission status: Time Limit Exceeded

Solution code:
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
for i in range(N):
    w[i], v[i] = [int(i) for i in input().split()]

dp = [[-float('inf')]*(W+1) for i in range(N+1)]
for i in range(W+1):
    dp[0][i] = 0

for i in range(1, N+1):
    for j in range(W+1):
        if j >= w[i-1]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
WV=[[int(x) for x in input().split()] for y in range(N)]

dp=[[0 for x in range(W+1)] for y in range(N+1)]
for i in range(N-1,-1,-1):
    for j in range(W+1):
        if j < WV[i][0]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-WV[i][0]]+WV[i][1])

print(dp[0][W])

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
weight = []
value = []

for n in range(0,N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)


dp = []

for w in range(0,N+1):
    dp.append([])

for i in range(0,W+1):
    for j in range(0,N+1):
        dp[j].append(0)


for i in range(0,N):
    for w in range(0,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]


print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
items = []
for n in range(N):
    items.append(tuple(map(int, input().split())))

dp = [[0] * (W+1) for x in range(N+1)]

for i, item in enumerate(items):
    wait, value = item
    for w in range(W+1):
        # choiced case
        if w - wait >= 0:
            dp[i+1][w] = max(dp[i+1][w], dp[i][w - wait] + value)
        # not choiced case
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])

print(max(sum(dp, [])))

Submission status: Time Limit Exceeded

Solution code:
# /user/bin/python
# -*- coding: utf-8 -*-
import math
import sys

n,w = map(int, sys.stdin.readline().rstrip().split())
weight = [0] * n
value = [0] * n
for i in range(n):
  weight[i], value[i] = list(map(int, sys.stdin.readline().rstrip().split()))

dp = [[0 for _ in range(w+1)] for _ in range(n+1)]

for i in range(n):
  for j in range(w+1):
    if j >= weight[i]:
      dp[i+1][j] = max(dp[i][j], dp[i][j-weight[i]]+value[i])
    else:
      dp[i+1][j] = dp[i][j]

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
def solve(n, w, items):
    # 1-origin
    dp = [[0] * (w + 1) for i in range(n + 1)]

    for i in range(1, n + 1):
        prev = i - 1
        weight, value = items[i - 1][0], items[i - 1][1]
        for j in range(1, w + 1):
            dp[i][j] = dp[prev][j]
            if j - weight >= 0:
                dp[i][j] = max(dp[i][j], dp[prev][j - weight] + value)

    return dp[n][w]


def main():
    n, w = map(int, input().split())

    items = []
    for i in range(n):
        items.append(list(map(int, input().split())))

    ans = solve(n, w, items)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]

dp = [[0 for i in range(W+1)] for j in range(N+1)]

for i in range(N) :
    weight_i,value_i = L[i]
    for weight in range(W+1) :
        if weight - weight_i >= 0 :
            dp[i+1][weight] = max(dp[i][weight], dp[i][weight - weight_i] + value_i)
        else :
            dp[i+1][weight] = dp[i][weight]

ans = dp[N][W]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
w, v = [[0]*N, [0]*N]
for n in range(N):
  w[n], v[n] = map(int, input().split())

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for n in range(N):
  for i in range(W+1):
    dp[n+1][i] = dp[n][i] if w[n] > i else max(dp[n][i-w[n]] + v[n], dp[n][i])

print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

input = sys.stdin.readline

N, MAX_W = map(int, input().split())

W = np.zeros(N, dtype=np.int64)
V = np.zeros(N, dtype=np.int64)

for i in range(N):
    W[i], V[i] = map(int, input().split())

dp = np.zeros((N+1, MAX_W+1), dtype=np.int64)

for i in range(N):
    for j in range(MAX_W+1):
        if j - W[i] >= 0:
            dp[i, j] = np.maximum(dp[i-1, j], dp[i-1, j-W[i]]+V[i])
        else:
            dp[i, j] = dp[i-1, j]

print(dp.max())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

N, MAX_W = map(int, input().split())

W = [0] * N
V = [0] * N

for i in range(N):
    W[i], V[i] = map(int, input().split())

dp = np.zeros((N+1, MAX_W+1), dtype=np.int64)

for i in range(N):
    for j in range(MAX_W+1):
        if j - W[i] >= 0:
            dp[i][j] = np.maximum(dp[i-1][j], dp[i-1][j-W[i]]+V[i])
        else:
            dp[i][j] = dp[i-1][j]

print(dp.max())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, MAX_W = map(int, input().split())

W = [0] * N
V = [0] * N

for i in range(N):
    W[i], V[i] = map(int, input().split())

dp = np.zeros((N+1, MAX_W+1), dtype=np.int64)

for i in range(N):
    for j in range(MAX_W+1):
        if j - W[i] >= 0:
            dp[i][j] = np.maximum(dp[i-1][j], dp[i-1][j-W[i]]+V[i])
        else:
            dp[i][j] = dp[i-1][j]

print(dp.max())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, MAX_W = map(int, input().split())

W = []
V = []

for i in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = np.zeros((N+1, MAX_W+1), dtype=np.int64)

for i in range(N):
    for j in range(MAX_W+1):
        if j - W[i] >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]]+V[i])
        else:
            dp[i][j] = dp[i-1][j]

print(dp.max())

Submission status: Time Limit Exceeded

Solution code:
class Solution(object):
    def knapsack1(self, w, vals):
        vals.insert(0, [0,0])
        # vals = sorted(vals, key=lambda x: x[0])
        dp = [[0 for _ in range(w+1)] for _ in range(len(vals))]

        for i in range(1, len(vals)):
            for j in range(1, w+1):

                curr_w, curr_v = vals[i]
                # print(i, j, curr_w, curr_v)
                if curr_w <= j:
                    # print('in 1')
                    dp[i][j] = max(dp[i-1][j], curr_v + dp[i-1][j-curr_w])
                else:
                    # print('in 2')
                    dp[i][j] = max(dp[i][j], dp[i-1][j])

        # print(dp)
        return dp[-1][-1]


if __name__ == '__main__':
    n, w = map(int, input().strip().split())
    vals = []
    for i in range(n):
        vals.append(list(map(int, input().strip().split())))
    sol = Solution()
    res = sol.knapsack1(w, vals)
    print(res)

Submission status: Time Limit Exceeded

Solution code:
n, w = list(map(int, input().strip().split()))
data = []
for i in range(n):
    data.append(list(map(int, input().strip().split())))

dp = {}

# i番目以降から重さをz以下にするように選ぶときの最大の価値
def rec(i, z):
    global dp
    if (i, z) in dp:
        return dp[(i, z)]

    if i == n:
        return 0

    # i 個目のものを入れられない場合
    elif data[i][0] > z:
        ret = rec(i + 1, z)
    else:
        # 入れられる場合、入れるときと入れないときのうち大きい方を返す
        # 入れるとき
        v1 = data[i][1] + rec(i + 1, z - data[i][0])
        # 入れないとき
        v2 = rec(i + 1, z)
        ret = max(v1, v2)
        dp[(i, z)] = ret
    return ret

print(rec(0, w))

Submission status: Time Limit Exceeded

Solution code:
n, w = list(map(int, input().strip().split()))
data = []
for i in range(n):
    data.append(list(map(int, input().strip().split())))

dp = {}

# i 個までで重さを z 以下にしたときの最大値
def rec(i, z):
    global dp
    if (i, z) in dp:
        return dp[(i, z)]

    if i < 0:
        ret = 0
    # i 個目のものを入れられない場合
    elif data[i][0] > z:
        ret = rec(i - 1, z)
    else:
        # 入れられる場合、入れるときと入れないときのうち大きい方を返す
        # 入れるとき
        v1 = data[i][1] + rec(i - 1, z - data[i][0])
        # 入れないとき
        v2 = rec(i - 1, z)
        ret = max(v1, v2)
        dp[(i, z)] = ret
    return ret

print(rec(n - 1, w))

Submission status: Time Limit Exceeded

Solution code:
n, w = list(map(int, input().strip().split()))
data = []
for i in range(n):
    data.append(list(map(int, input().strip().split())))

dp = {}

# i 個までで重さを z 以下にしたときの最大値
def rec(i, z):
    if (i, z) in dp:
        return dp[(i, z)]

    if i < 0:
        ret = 0
    # i 個目のものを入れられない場合
    elif data[i][0] > z:
        ret = rec(i - 1, z)
    else:
        # 入れられる場合、入れるときと入れないときのうち大きい方を返す
        # 入れるとき
        v1 = data[i][1] + rec(i - 1, z - data[i][0])
        # 入れないとき
        v2 = rec(i - 1, z)
        ret = max(v1, v2)
        dp[(i, z)] = ret
    return ret

print(rec(n - 1, w))

Submission status: Time Limit Exceeded

Solution code:
n, w = list(map(int, input().strip().split()))
data = []
for i in range(n):
    data.append(list(map(int, input().strip().split())))

dp = [None] * n

# i 個までで重さを z 以下にしたときの最大値
def rec(i, z):
    if i < 0:
        return 0
    # i 個目のものを入れられない場合
    if data[i][0] > z:
        return rec(i - 1, z)

    # 入れられる場合、入れるときと入れないときのうち大きい方を返す
    # 入れるとき
    v1 = data[i][1] + rec(i - 1, z - data[i][0])
    # 入れないとき
    v2 = rec(i - 1, z)
    return max(v1, v2)

print(rec(n - 1, w))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    dp = {}
    for i in range(W + 1):
        dp[0, i] = 0
    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]

N, W = map(int, input().split())
w = {}
v = {}
for i in range(N):
    w[i], v[i] = map(int, input().split())
print(solve())

Submission status: Time Limit Exceeded

Solution code:
import itertools as itr
n, w = list(map(int, input().split()))
warr = [0]*(n+1)
varr = [0]*(n+1)
for i in range(n):
    wi, vi = list(map(int, input().split()))
    warr[i+1] = wi
    varr[i+1] = vi
    
dp = [[0]*(w+1) for _ in range(n+1)]

for i, j in itr.product(range(1,n+1), range(1,w+1)):
        jw = j-warr[i]
        if jw <0:
            dp[i][j] = dp[i-1][j]
            continue
        dp[i][j] = max(dp[i-1][jw] + varr[i], dp[i-1][j])
        
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 19:31:10 2019
Knapsack1
@author: maezawa
"""

n, w = list(map(int, input().split()))
warr = [0]*(n+1)
varr = [0]*(n+1)
for i in range(n):
    wi, vi = list(map(int, input().split()))
    warr[i+1] = wi
    varr[i+1] = vi
    
dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,w+1):
        jw = j-warr[i]
        if jw <0:
            continue
        dp[i][j] = max([dp[k][jw] + varr[i] for k in range(i)])
        dp[i][j] = max(dp[i][j], dp[i-1][j])
        
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
N, W = [int(i) for i in input().split()]
V = [[int(i) for i in input().split()] for j in range(N)]

DP = [0] * (W+1)
V.sort(key=lambda x: x[1])

for w, v in V:
    for i in range(W, -1, -1):
        if w > i:
            break
        DP[i] = max(DP[i], DP[i-w] + v)

print(DP[W])

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
wv = []
for i in range(N):
  wv.append(list(map(int,input().split())))
dp = []
for i in range(N+1):
  dp.append([0 for _ in range(W+1)])
for i in range(N-1,-1,-1):
  for j in range(0,W+1):
    if j < wv[i][0]:
      dp[i][j] = dp[i+1][j]
    else:
      dp[i][j] = max(dp[i+1][j],dp[i+1][j-wv[i][0]]+wv[i][1])
print(dp[0][W])

Submission status: Time Limit Exceeded

Solution code:
import sys
def solve(i,j,dp,w,v):
    if dp[i][j]!=0:
        return dp[i][j]
    else:
        if i==0:
            dp[i][j]=0
            return dp[i][j]
        if j<w[i-1]:
            dp[i][j]=solve(i-1,j,dp,w,v)
            return dp[i][j]
        else:
            dp[i][j]=max(solve(i-1,j,dp,w,v),solve(i-1,j-w[i-1],dp,w,v)+v[i-1])
            return dp[i][j]
sys.setrecursionlimit(10000000)
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[[0 for j in range(W+1)] for i in range(N+1)]
print(solve(N,W,dp,w,v))

Submission status: Time Limit Exceeded

Solution code:
def solve(i,j,dp,w,v):
    if dp[i][j]!=0:
        return dp[i][j]
    else:
        if i==0:
            dp[i][j]=0
            return dp[i][j]
        if j<w[i-1]:
            dp[i][j]=solve(i-1,j,dp,w,v)
            return dp[i][j]
        else:
            dp[i][j]=max(solve(i-1,j,dp,w,v),solve(i-1,j-w[i-1],dp,w,v)+v[i-1])
            return dp[i][j]
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[[0 for j in range(W+1)] for i in range(N+1)]
print(solve(N,W,dp,w,v))

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[[0 for j in range(W+1)] for i in range(N+1)]
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])
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int,input().split())
stuff = [ list(map(int, input().split())) for i in range(n)]
dp = [0]*(w+1)
for i in range(n):
    for j in range(w,0,-1):
        if dp[j] != 0 and j+stuff[i][0] <= w:
            dp[j+stuff[i][0]] = max(dp[j+stuff[i][0]],dp[j]+stuff[i][1])
    dp[stuff[i][0]] = max(dp[stuff[i][0]],stuff[i][1])
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
###modular exponentiation: a^n % M
#pow(a, n, M) 
### gcd: gcd(a, b)
#import fractions
#fractions.gcd(a, b)
### LCM (M, N)
#lcm = M*N/fractions.gcd(M, N)
INF = 1000000000+5

def get_res(N, W, A):
    DP = []
    for _ in range(N+1):
        L = [0]*(W+1)
        DP.append(L)
    for i in range(1, N+1):
        # DP[i] = minimum penalty incurred in reaching stone i from stone 1
        wi = A[i-1][0]
        vi = A[i-1][1]
        for j in range(1, W+1):
            if wi > j:
                DP[i][j] = DP[i-1][j]
            else:
                DP[i][j] = max(DP[i-1][j], vi + DP[i-1][j-wi])
            #print(DP)


    return DP[N][W]

N, W = [int(s) for s in input().split(" ")]
A = []
for _ in range(N):
    L = [int(s) for s in input().split(" ")]
    A.append(L)
#print(A)
result = get_res(N, W, A)
print("{}".format(result))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n, w =  [int(x) for x in stdin.readline().rstrip().split()]
item = []
for i in range(n):
    item.append([int(x) for x in stdin.readline().rstrip().split()])
dp = [[0] * (w + 1) for i in range(n + 1)]
lw = 0
for i in range(1, n + 1):
    for maxw in range(w + 1):
        inw = maxw - item[i - 1][0]
        dp[i][maxw] = dp[i-1][maxw]
        if inw >= 0:
            ndp = dp[i - 1][inw] + item[i - 1][1]
            if dp[i][maxw] < ndp:
                dp[i][maxw] = ndp
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n, w =  [int(x) for x in stdin.readline().rstrip().split()]
item = []
for i in range(n):
    item.append([int(x) for x in stdin.readline().rstrip().split()])
dp = [[0] * (w + 1) for i in range(n + 1)]
lw = 0
for i in range(1, n + 1):
    for maxw in range(w + 1):
        inw = maxw - item[i - 1][0]
        dp[i][maxw] = max(dp[i][maxw], dp[i-1][maxw])
        if inw >= 0:
            #print(dp[i][maxw], dp[i - 1][inw] + item[i - 1][1])
            dp[i][maxw] = max(dp[i][maxw], dp[i - 1][inw] + item[i - 1][1])
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N)]

# init
first_item = items[0]
for i in range(W+1):
    if i >= first_item[0]:
        dp[0][i] = first_item[1]

# update
for i in range(1, N):
    for w in range(W+1):
        if w-items[i][0] >= 0:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-items[i][0]]+items[i][1])
        else:
            dp[i][w] = dp[i-1][w]

print(max(dp[N-1]))

Submission status: Time Limit Exceeded

Solution code:
# D

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (W+1) for _ in range(N)]
for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            dp[i][j] = max(dp[i-1][j-w[i]] + v[i], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
N,W= [int(x) for x in input().split()]

weights=[0]*N
values=[0]*N
dp=[]

for i in range(N):
    weights[i],values[i] =[int(x) for x in input().split()]
    dp.append([0]*(W+1))


for j in range(W+1):
    if(j>=weights[0]):
        dp[0][j]=values[0]

for i in range(1,N):

    for j in range(W+1):

        if(j-weights[i]>=0):
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-weights[i]] + values[i])
        else:
            dp[i][j]=dp[i-1][j]



print(dp[N-1][W])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


inf = float('inf')


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_list_of_int():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


# inputs
N, W = 0, 0
Ws, Vs = [0], [0]


def set_inputs():
    global N, W, Ws, Vs
    N, W = get_list_of_int()
    ws, vs = [], []
    for _ in range(N):
        w, v = get_list_of_int()
        ws.append(w)
        vs.append(v)
    Ws, Vs = ws, vs


def main():
    set_inputs()
    values = [0] * (W + 1)
    items = [set()] * (W + 1)
    for w in range(1, W + 1):
        values[w], items[w] = max((values[w - Ws[i]] + Vs[i], items[w - Ws[i]] | {i}) if w - Ws[i] >= 0 and i not in items[w - Ws[i]] else (values[w-1], items[w-1]) for i in range(N))
    print(values[W])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, mw = map(int, input().split())
w, v = [], []
for _ in range(n):
    x, y = map(int, input().split())
    w.append(x)
    v.append(y)
dp = [[0 for _ in range(mw+1)] for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(mw+1):
        if w[i-1] <= j:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n][mw])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, W = map(int, input().split())
    wl = []
    vl = []
    for _ in range(N):
        w, v = map(int, input().split())
        wl.append(w)
        vl.append(v)
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(W + 1):
            if wl[i] > j:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wl[i]] + vl[i])
    print(dp[N][W])


main()