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:
def knapcalc(weights, vals, capacity):
    n = len(weights)
    cache = [[None]*(n+1) for i in range(capacity+1)]
    return knapcalc_(weights, vals, capacity, len(vals), cache=cache, depth="")

def knapcalc_(weights, vals, capacity_left, max_item, cache, depth):
    # print(f"{depth}knapcalc_(capa: {capacity_left}, max_item: {max_item}]")
    if (capacity_left <= 0):
        return 0

    if (max_item == 0):
        return 0

    if cache[capacity_left][max_item]:
        return cache[capacity_left][max_item]

    best_res = 0
    for i in range(0, max_item):
        if capacity_left - weights[i] >= 0:
            sub_res = knapcalc_(weights, vals, capacity_left - weights[i], max_item=i, cache=cache, depth=depth+" ") + vals[i]
            if (sub_res > best_res):
                best_res = sub_res

    cache[capacity_left][max_item] = best_res
    # print(f"{depth}cache[capa: {capacity_left}, limit: {max_item}]={res}")
    return best_res

if __name__ == "__main__":
    n, capacity = list(map(int, input().split(" ")))
    weights = []
    vals = []
    for i in range(n):
        w,v = list(map(int, input().split(" ")))
        weights.append(w)
        vals.append(v)
    res = knapcalc(weights, vals, capacity)
    print(res)

Submission status: Time Limit Exceeded

Solution code:
def knapcalc(weights, vals, capacity):
    return knapcalc_(weights, vals, capacity, len(vals), cache=dict(), depth="")

def knapcalc_(weights, vals, capacity_left, max_item, cache, depth):
    # print(f"{depth}knapcalc_(capa: {capacity_left}, max_item: {max_item}]")
    if (capacity_left <= 0):
        return 0

    if (max_item == 0):
        return 0

    if (capacity_left, max_item) in cache:
        return cache[(capacity_left, max_item)]

    if (max_item == 0):
        import pdb; pdb.set_trace()

    res = max([
        knapcalc_(weights, vals, capacity_left - weights[i], max_item=i, cache=cache, depth=depth+" ") + vals[i]
        for i in range(0, max_item)
        if capacity_left - weights[i] >= 0
    ] + [0])

    cache[capacity_left, max_item] = res
    # print(f"{depth}cache[capa: {capacity_left}, limit: {max_item}]={res}")
    return res

if __name__ == "__main__":
    n, capacity = list(map(int, input().split(" ")))
    weights = []
    vals = []
    for i in range(n):
        w,v = list(map(int, input().split(" ")))
        weights.append(w)
        vals.append(v)
    res = knapcalc(weights, vals, capacity)
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
import numpy as np

def knapsack(W, wt, val, n):
    # Base Case 
    if n == 0 or W == 0 : 
        return 0
  
    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if (wt[n-1] > W): 
        return knapsack(W , wt , val , n-1) 
  
    # return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included 
    else: 
        return max(val[n-1] + knapsack(W-wt[n-1] , wt , val , n-1), 
                   knapsack(W , wt , val , n-1))
def main():
    lines = []
    for line in sys.stdin:
        lines.append([int(i) for i in line.strip().split(' ')])
    n = lines[0][0]
    w = lines[0][1]
    
    wt = np.array(lines[1:])[:,0]
    val = np.array(lines[1:])[:,1]
    print(knapsack(w, wt, val, n))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
weight = []
value = []
for i in range(n):
    tmp1,tmp2 = map(int,input().split())
    weight.append(tmp1)
    value.append(tmp2)

#dp[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
dp = [[0 for i in range(w+1)] for j in range(n+1)]
dp[1][weight[0]] = value[0]

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

Submission status: Time Limit Exceeded

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

dp = [0] * (w + 1)

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

print(dp[w])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
dp = [0] * (W + 1)
WV = []
for i in range(N):
  WV.append(map(int, input().split()))
 
for i in range(N):
    wi, vi = WV[i]
    for w in range(W, wi-1, -1):
        newValue = dp[w-wi] + vi
        if dp[w] < newValue:
            dp[w] = newValue
print(dp[-1])

Submission status: Time Limit Exceeded

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


#dp[i][j]:i番目(1<=i<=N)までの品物を重さの総和がj以下となるように選ぶときの価値の総和の最大値
dp = [[0] * (W + 1) for i in range(N + 1)]

#配る
for i in range(N):
    for j in range(W + 1):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j + w[i+1] > W: continue
        dp[i+1][j+w[i+1]] = max(dp[i+1][j+w[i+1]], dp[i][j]+v[i+1])

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
dp = [0] * (W + 1)

for i in range(N):
    wi, vi = map(int, input().split())
    for w in range(W, wi-1, -1):
        newValue = dp[w-wi] + vi
        if dp[w] < newValue:
            dp[w] = newValue
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
# # Educational DP Contest D
# 方針：dp[i][w] := i番目の物の中から，重さwを超えない時の価値の最大値
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

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

for i in range(N):
    for w in range(W+1):
        if w >= wv[i][0]:       # 重さwv[i][0]を入れられるか
            dp[i+1][w] = max(dp[i][w - wv[i][0]] + wv[i][1], 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()) 
dp = [[0 for i in range(W + 1)] for j in range(N+1)]
weight = []
value = []
for i in range(N):
    w,v = map( int, input().split() )
    weight.append(w)
    value.append(v)

for i in range(1,N+1):
    for j in range(0,W+1):
        if j - weight[i-1] >= 0:
            dp[i][j] = max( dp[i-1][ j - weight[i-1] ] + value[i-1], dp[i][j])
        dp[i][j] = max(dp[i][j],dp[i-1][j])
        
print(dp[N][W])

Submission status: Time Limit Exceeded

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

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

def process(N,W):
  box=[0]*(W+1)
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(W,0,-1):
      idx = j-w
      if idx<0:
        break
      else:
        box[j] = max(box[j],box[idx]+v)
  return box[-1]

print(process(N,W))

Submission status: Time Limit Exceeded

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

N,W=map(int,input().split())
box=[0]*(W+1)

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

Submission status: Time Limit Exceeded

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

N,W=map(int,input().split())
box=[[0]*(W+1) for i in range(N+1)]

for i in range(N):
  w,v=map(int,input().split())
  for j in range(W+1):
    box[i+1][j]=max(box[i+1][j],box[i][j])
    total = j+w
    if total>W:
      continue
    else:
      box[i+1][total]=max(box[i][total], box[i][j]+v)
print(box[-1][-1])

Submission status: Time Limit Exceeded

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


def ans(n, w):
    dp = [0] * (w+1)
    for _ in range(n):
        wi, vi = map(int, input().split())
        for i in range(wi, w+1):
            if dp[i-wi] < dp[i] + vi:
                dp[i-wi] = dp[i] + vi
    return dp[0]


N, W = map(int, input().split())
print(ans(N, W))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, W = map(int, input().split())
    dp = [0] * (W + 1)
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(w, W+1):
            j = dp[i]
            if dp[i-w] < j + v:
                dp[i-w] = j + v

    print(max(dp))


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, W = map(int, input().split())
dp = [0] * (W + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for i in range(w, W+1):
        j = dp[i]
        if j == -1:
            continue
        if dp[i-w] < j + v:
            dp[i-w] = j + v

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

memo = {}

def solve(i, w_):
	global w, v, N, W
	if (i, w_) not in memo:
		if i < N:
			if w_ + w[i] <= W:
				result = max(solve(i + 1, w_), v[i] + solve(i + 1, w_ + w[i]))
			else:
				result = solve(i + 1, w_)
		else:
			result = 0
		memo[(i, w_)] = result
		return result
	else:
		return memo[(i, w_)]

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

print(solve(0, 0))

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  sys.setrecursionlimit(10**7)
  N,W=list(map(int,sys.stdin.readline().split()))

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

  WL=[0]* N
  VL=[0]*N

  for i in range(N):
      w,v=list(map(int,sys.stdin.readline().split()))
      WL[i]=w
      VL[i]=v


  def dfs(W,i):
      if i==N:
          return 0
      if dp[W][i]:
          return dp[W][i]
      if W-WL[i]>=0:
          dp[W][i]=max(dfs(W,i+1),dfs(W-WL[i],i+1)+VL[i])
          return dp[W][i]
      else:
          dp[W][i]=dfs(W,i+1)
          return dp[W][i]

  print(dfs(W,0))

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  sys.setrecursionlimit(10**7)
  N,W=list(map(int,sys.stdin.readline().split()))

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

  WL=[0]* N
  VL=[0]*N

  for i in range(N):
      w,v=list(map(int,sys.stdin.readline().split()))
      WL[i]=w
      VL[i]=v


  def dfs(W,i):
      if i==N:
          return 0
      if dp[W][i]:
          return dp[W][i]
      if W-WL[i]>=0:
          dp[W][i]=max(dfs(W,i+1),dfs(W-WL[i],i+1)+VL[i])
          return dp[W][i]
      else:
          dp[W][i]=dfs(W,i+1)
          return dp[W][i]

  print(dfs(W,0))

main()

Submission status: Time Limit Exceeded

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

# dp[i][j] := i番目の以前の品物から、重さがj以下になるような最大の価値
dp = [[-1]*(w+1) for _ 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):
        # 重さjより上なら、選ばない
        if j < a[i-1][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i-1][0]] + a[i-1][1])
            
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
N,W=list(map(int,sys.stdin.readline().split()))

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

WL=[0]* N
VL=[0]*N

for i in range(N):
    w,v=list(map(int,sys.stdin.readline().split()))
    WL[i]=w
    VL[i]=v


def dfs(W,i):
    if i==N:
        return 0
    if dp[W][i]:
        return dp[W][i]
    if W-WL[i]>=0:
        dp[W][i]=max(dfs(W,i+1),dfs(W-WL[i],i+1)+VL[i])
        return dp[W][i]
    else:
        dp[W][i]=dfs(W,i+1)
        return dp[W][i]

print(dfs(W,0))

Submission status: Time Limit Exceeded

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

#V = [0 for _ in range(10**5)]
V = []
W = []
dp = [[0 for _ in range(Weight+1)] for _ in range(N+1)]

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

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


print(dp[N][Weight])

Submission status: Time Limit Exceeded

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

#V = [0 for _ in range(10**5)]
V = []
W = []

for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
def dp(i, w):
    if i<N and w-W[i]>=0:
        ans = max(dp(i+1, w), dp(i+1, w-W[i])+V[i])
    elif i<N:
        ans = dp(i+1, w)
    else:
        ans = 0
    return ans

print(dp(0, Weight))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)
dp = np.zeros((N+1, W+1),dtype=int)

for i in range(N):
    w[i], v[i] = map(int, input().split())
    for j in range(W+1):
        if w[i] > j:
            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:
import numpy as np

N, W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)
dp = np.zeros((N+1, W+1),dtype=int)

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

for i in range(N):
    for j in range(W+1):
        if w[i] > j:
            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:
import sys
input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

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

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

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

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

    for i in range(N, -1, -1):
        for j in range(W + 1):
            if i == N:
                try:
                    dp[j][i] = 0
                except IndexError:
                    print(j)
            else:
                if shina[i][0] > j:
                    dp[j][i] = dp[j][i + 1]
                else:
                    dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from functools import lru_cache
sys.setrecursionlimit(10 ** 8)

shina = []
N = 0


@lru_cache(maxsize=None)
def solve(i, j):
    global N
    if i == N:
        return 0

    if shina[i][0] > j:
        return solve(i + 1, j)

    return max(solve(i + 1, j), solve(i + 1, j - shina[i][0]) + shina[i][1])


def main():
    global N
    N, W = [int(x) for x in input().split()]
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    ans = solve(0, W)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from functools import lru_cache
sys.setrecursionlimit(10 ** 8)

shina = []


@lru_cache(maxsize=None)
def solve(i, j):
    if i == len(shina):
        return 0

    if shina[i][0] > j:
        return solve(i + 1, j)

    return max(solve(i + 1, j), solve(i + 1, j - shina[i][0]) + shina[i][1])


def main():
    N, W = [int(x) for x in input().split()]
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    ans = solve(0, W)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp = [0] * (W + 1)
weights2check = [0]
for _ in range(N):
    w, v = map(int, input().split())
    new_weights2check = []
    for k in weights2check:
        if k + w <= W:
            dp[k + w] = max(dp[k + w], dp[k] + v)
            new_weights2check.append(k + w)

    weights2check += new_weights2check


ans = max(dp[i] for i in weights2check)
print(ans)

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):
  t1, t2 = map(int, input().split())
  w.append(t1)
  v.append(t2)
dp = np.zeros((n, max_w+1)) #dp[item, load]
for i in range(w[0], max_w+1):
  dp[0,i] = v[0]
for i in range(1, n):
  for j in range(0, max_w+1):
    t1 = 0 
    if j >= w[i]:
      t1 = dp[i-1, j-w[i]] + v[i]
    t2 = dp[i-1, j]
    dp[i, j] = max(t1, t2)
print(int(dp[n-1, max_w]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from functools import lru_cache

shina = []


@lru_cache(maxsize=None)
def solve(i, j):
    if i == len(shina):
        return 0

    if shina[i][0] > j:
        return solve(i + 1, j)

    return max(solve(i + 1, j), solve(i + 1, j - shina[i][0]) + shina[i][1])


def main():
    N, W = [int(x) for x in input().split()]
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    ans = solve(0, W)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def solve(i, j, shina):
    if i == len(shina):
        return 0

    if shina[i][0] > j:
        return solve(i + 1, j, shina)

    return max(solve(i + 1, j, shina), solve(i + 1, j - shina[i][0], shina) + shina[i][1])


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    ans = solve(0, W, shina)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    ans = 0
    for i in range(2 ** N):
        weight = 0
        value = 0
        for j in range(N):
            if (i >> j) & 1:
                weight += shina[j][0]
                value += shina[j][1]
                if weight > W:
                    value = 0
                    break

        ans = max(ans, value)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N, capacity = inputIntList()
    w = [0 for _ in range(N)]
    v = [0 for _ in range(N)]
    for i in range(N):
        w[i], v[i] = inputIntList()

    dp = [[0 for _ in range(capacity + 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(capacity + 1):
            if j < w[i]:
                dp[i + 1][j] = dp[i][j]
            else:

                dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j])
            # print(dp)

    return dp[N][capacity]


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp=np.zeros([N+1, W+1])

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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


print(DP())

Submission status: Time Limit Exceeded

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

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

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


print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def main():
    N,W = map(int,input().split())
    wvlist = []
    dp =[[0 for i in range(W+1)] for j in range(N+1)]
    for i in range(N):
        lista = list(map(int,input().split()))
        wvlist.append(lista)
    for i in range(N):
        for j in range(W+1):
            if wvlist[i][0] <= j:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j-wvlist[i][0]]+wvlist[i][1])
            else:
                dp[i+1][j] = dp[i][j]
    print(np.amax(dp))            
        
    
    
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def main():
    N,W = map(int,input().split())
    wvlist = []
    dp =[[0 for i in range(W+1)] for j in range(N+1)]
    for i in range(N):
        lista = list(map(int,input().split()))
        wvlist.append(lista)
    sumax = sum(wvlist[i][0] for i in range(N))
    sumin = min(wvlist[i][0] for i in range(N))
    vamax = sum(wvlist[i][1] for i in range(N))
    if sumax <= W:
        print(vamax)
    elif sumin > W:
        print(0)
    else:
        for i in range(N):
            for j in range(W+1):
                if wvlist[i][0] <= j:
                    dp[i+1][j] = max(dp[i+1][j],dp[i][j-wvlist[i][0]]+wvlist[i][1])
                else:
                    dp[i+1][j] = dp[i][j]
        print(np.amax(dp))            
        
    
    
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,W=map(int,input().split())
    WV=[tuple(map(int,input().split())) for _ in range(n)]

    dp=[-INF]*(W+1)
    dp[0]=0
    for w,v in WV:
        for x in range(W,-1,-1):
            if(x+w<=W):
                dp[x+w]=max(dp[x+w],dp[x]+v)

    print(max(dp))
resolve()

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
w = list()
v = list()
for i in range(N):
    a,b = map(int,input().split())
    w.append(a)
    v.append(b)

dp = [[0 for i in range(10**5+3)]for i in range(N+1)]

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
W=[]
V=[]

for i in range(n):
	a,b=map(int,input().split())
	W.append(a)
	V.append(b)

def knap(n,w):
	dp=[[0]*(w+1) for i in range(n+1)]
	for i in range(n):
		for j in range(w+1):
			if j<W[i-1]:
				dp[i+1][j]=dp[i][j]
			else:
				dp[i+1][j]=max(dp[i][j],dp[i][j-W[i-1]]+V[i-1])
	return dp[n][w]

print(knap(n,w))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# dp[i][j]: i+1個目までの品物で重量の総和がj以下である時の価値の最大値

N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    tmp = list(map(int, input().split()))
    w.append(tmp[0])
    v.append(tmp[1])
    
dp = np.zeros(shape=(N+1, W+1), dtype=int)
for i in range(N):
    for j in range(W+1):
        if w[i] <= j:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
        else:
            #dp[i+1][j] = max(dp[i][j], dp[i+1][j])
            dp[i+1][j] = dp[i][j]
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0

  #DP
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: #dp[i][w-weight[i]の状態に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]
n1,w1=map(int,input().split())
lw=[]
lv=[]
for i in range(n1):
  w,v=map(int,input().split())
  lw.append(w)
  lv.append(v)
print(knapsack(n1,w1,lw,lv))

Submission status: Time Limit Exceeded

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

    dp = [[0 for j in range(W)] for i in range(N)]
    dp[0][data[0][0]-1:] = [data[0][1]]*len(dp[0][data[0][0]-1:])
    #print(dp)
    for i in range(1,N):
        for sum_w in range(W):
            w = sum_w - data[i][0]
            if w<0:
                ans = dp[i-1][sum_w]
            else:
                ans = max(dp[i-1][sum_w],dp[i-1][w]+data[i][1])
            dp[i][sum_w] = ans    
    print(dp[-1][-1])


if __name__ == '__main__':
    test()

Submission status: Time Limit Exceeded

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


dp = [[0 for j in range(W)] for i in range(N)]
dp[0][data[0][0]-1:] = [data[0][1]]*len(dp[0][data[0][0]-1:])
#print(dp)
for i in range(1,N):
    for sum_w in range(W):
        w = sum_w - data[i][0]
        if w<0:
            ans = dp[i-1][sum_w]
        else:
            ans = max(dp[i-1][sum_w],dp[i-1][w]+data[i][1])
        dp[i][sum_w] = ans    
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
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=[[-1 for _ in range(W+1)] for _ in range(N+1)]
for i in range(W+1):
    dp[N][i] = 0
for i in range(0,N)[::-1]:
    for j in range(W+1):
        if j < w[i]:
            dp[i][j]=dp[i+1][j]
        else:
            dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
print(dp[0][-1])

Submission status: Time Limit Exceeded

Solution code:
n, w = [int(i) for i in input().split()]
a = [0] * (w + 1)
for _ in range(n):
    b, c = [int(i) for i in input().split()]
    for i in reversed(range(w + 1)):
        if i + b >= w + 1:
            continue
        d = i + b
        a[d] = max(a[d], a[i] + c)
print(a[-1])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

"""
20191120
構成法
穴あき
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

    # initialize
    dp = [[None for _ in range(W+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    if W >= ws[0]:
        dp[0][ws[0]] = vs[0]
        existance[0].add(ws[0])

    for n in range(N-1):
        for w in existance[n]:
            # not-use-update
            if dp[n+1][w] is None:
                dp[n+1][w] = dp[n][w]
            else:
                dp[n+1][w] = max(dp[n][w], dp[n+1][w])
            existance[n+1].add(w)

            # use-update
            if w + ws[n+1] <= W:
                if dp[n+1][w+ws[n+1]] is None:
                    dp[n+1][w+ws[n+1]] = dp[n][w] + vs[n+1]
                else:
                    dp[n+1][w+ws[n+1]] = max(dp[n][w] + vs[n+1], dp[n+1][w+ws[n+1]])
                existance[n+1].add(w+ws[n+1])
    # print(np.array(dp))

    ans = 0
    for w in range(1, W+1):
        if dp[-1][w] is not None and dp[-1][w] > ans:
            ans = dp[-1][w]

    return ans


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

# import numpy as np

"""
20191119
24分ギブアップ
質問

20191120
12分
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

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

    for n in range(N):
        for w in range(W+1):
            if w >= ws[n]:
                dp[n][w] = max(dp[n-1][w-ws[n]]+vs[n], dp[n-1][w])  # use or not use
            else:
                dp[n][w] = dp[n-1][w]  # not use

    return max(dp[-1])


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, W = list(map(int, input().split()))
w = [0 for i in range(n + 1)]
v = [0 for i in range(n + 1)]
for i in range(n):
    w[i + 1], v[i + 1] = list(map(int, input().split()))
dp = np.zeros((n + 1,W+1))
for i in range(1,n+1):
    for j in range(1,W+1):
        if w[i] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
print(int(dp[n][W]))