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^9

1 \leq w_i \leq W

1 \leq v_i \leq 10^3

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

1 1000000000
1000000000 10

Sample Output 2

10

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 main():
    N, W = map(int, input().split())
    #dp[v] vとなる最小のＷ
    dp = [10**9+1 for _ in range(10**5+1)]
    for _ in range(N):
        w,v = map(int, input().split())
        for val in range(10**5, 1, -1):
            if val - v < 1:
                break
            dp[val] = min(dp[val], dp[val - v] + w)
        if dp[v] > w:
            dp[v] = w
    ans = 0
    for v, w in enumerate(dp):
        if w <= W:
            ans = max(ans, v)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, W = map(int, input().split())
#dp[v] vとなる最小のＷ
dp = np.full(10**5+1, 10**9+1, dtype=np.int64)
for _ in range(N):
    w,v = map(int, input().split())
    for val in range(10**5, 1, -1):
        if val - v < 1:
            break
        dp[val] = min(dp[val], dp[val - v] + w)
    if dp[v] > w:
        dp[v] = w
print(max(np.where(dp <= W)[0]))

Submission status: Time Limit Exceeded

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

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

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

            
print(max(dp[N]))

Submission status: Time Limit Exceeded

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

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

W0 = WV[0][0]
V0 = WV[0][1]

def initial(w):
    if w >= W0:
        return V0
    else:
        return 0
dp[0] = [initial(w) for w in range(W+1)]

def calcu(i,w):
    if dp[i][w] != -1:
        return dp[i][w]

    w_i = WV[i][0]
    if w >= w_i:
        res = max(calcu(i-1, w-w_i)+WV[i][1], calcu(i-1,w))

    else:
        res = calcu(i-1,w)
    dp[i][w] = res
    return res

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
INF = 10**10
V = [v for w, v in wv]
v_max = sum(V)
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for i in range(N):
    for j in range(wv[i][1]):
        dp[i+1][j] = dp[i][j]
    for j in range(wv[i][1], v_max+1):
        dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
for j in range(v_max, 0, -1):
    if dp[N][j] <= W:
        print(j)
        break

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
INF = 10**10
v_max = 10**5
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for i in range(N):
    for j in range(wv[i][1]):
        dp[i+1][j] = dp[i][j]
    for j in range(wv[i][1], v_max+1):
        dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
for j in range(v_max, 0, -1):
    if dp[N][j] <= W:
        print(j)
        break

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
V = [v for w, v in wv]
INF = 10**10
v_max = sum(V)
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for i in range(N):
    for j in range(v_max+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
            #print(i, j, dp[i+1][j], dp[i][j], wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
        if dp[i+1][j] <= W and j > ans:
            ans = j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
V = [v for w, v in wv]
INF = 10**10
v_max = sum(V)
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(v_max+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
            #print(i, j, dp[i+1][j], dp[i][j], wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
ans = 0
for v, w in enumerate(dp[N]):
    if w <= W and v > ans:
        ans = v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
INF = 10**10
v_max = 10**5
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for i in range(N):
    for j in range(v_max+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
            #print(i, j, dp[i+1][j], dp[i][j], wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
        if dp[i+1][j] <= W:
            ans = j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
INF = 10**10
v_max = 10**5
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(v_max+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
            #print(i, j, dp[i+1][j], dp[i][j], wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
ans = 0
for v, w in enumerate(dp[N]):
    if w<= W and v > ans:
        ans = v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,io
from functools import lru_cache
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
N,W=reads()
weight,value=[0]*N,[0]*N
for i in range(N):
    weight[i],value[i]=reads()
@lru_cache(None)
def dp(i,w):
  res=0
  if  i==0:
    return 0
  if w-weight[i-1]>=0:
    com=dp(i-1,w-weight[i-1])+value[i-1]
  else:
    com=0
  return max(dp(i-1,w),com)
print(dp(N,W))
#print("{}".format(dp(N,W)))

Submission status: Time Limit Exceeded

Solution code:
import sys,io
from functools import lru_cache
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
N,W=reads()
weight,value=[0]*N,[0]*N
for i in range(N):
    weight[i],value[i]=reads()
dp=[[ 0 for _ in  range(W+1) ] for _ in range(N+1)]
for i in range(N):
  for k in range(1,W+1):
    if (k >= weight[i]) :dp[i+1][k] = max(dp[i][k-weight[i]] + value[i], dp[i][k])
    else :dp[i+1][k] = dp[i][k]
print("{}".format(dp[N][W]))

Submission status: Time Limit Exceeded

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n,w=n1()
WV=n3(n)

W=[0]
W.extend([x[0] for x in WV])
V=[0]
V.extend([x[1] for x in WV])

max_v=sum(V)
dp=[[0]+[float("inf")]*(max_v) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,max_v+1):
        if j-V[i]>=0:
            dp[i][j]=min(dp[i-1][j-V[i]]+W[i],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
#     print(dp[i])

for i in range(max_v+1):
    if dp[n][i]<=w:
        ans=i
print(ans)

Submission status: Time Limit Exceeded

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[value] - minimum weight that achieves value
    OPT[value] = OPT[value-v[i]]
    """
    N, W = read_ints()
    max_value = 1000*N+1
    dp = [10**12+1]*max_value
    dp[0] = 0
    for i in range(N):
        w, v = read_ints()
        for j in range(max_value-1, -1, -1):
            if j >= v:
                dp[j] = min(dp[j], dp[j-v]+w)
    ans = 0
    for j in range(max_value):
        if dp[j] <= W:
            ans = j
    return ans


if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
l=input().split()
n=int(l[0])
W=int(l[1])
lweight=[]
lvalue=[]
for i in range(n):
	l=input().split()
	u=int(l[0])
	v=int(l[1])
	lweight.append(u)
	lvalue.append(v)
dp=[[0 for i in range(W+1)] for i in range(n+1)]
for i in range(n+1):
	dp[i][0]=0
for j in range(W+1):
	dp[0][j]=0
for i in range(1,n+1):
	for j in range(1,W+1):
		if(j>=lweight[i-1]):
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-lweight[i-1]]+lvalue[i-1])
		else:
			dp[i][j]=dp[i-1][j]
print(dp[n][W])

Submission status: Time Limit Exceeded

Solution code:
n,v=[int(k) for k in input().split()]
li=[]
for i in range(n):
  li.append([int(k) for k in input().split()])
  
dp=[[0 for i in range(v+1)] for j in range(n+1)]
for a in range(1,n+1):
  for b in range(1,v+1):
    if(li[a-1][0]<=b):
      dp[a][b]=max(li[a-1][1]+dp[a-1][b-li[a-1][0]],dp[a-1][b])
    else:
      dp[a][b]=dp[a-1][b]
print(dp[n][v])

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
box = []
v = []
for i in range(n):
  W,V = map(int,input().split())
  box.append([W,V])
  v.append(V)
vmax = n*max(v)
inf = float('inf')
dp = [[inf for i in range(vmax+1)] for j in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
  for j in range(vmax+1):
    if j >= box[i-1][1]:
      dp[i][j] = min(dp[i-1][j-box[i-1][1]] + box[i-1][0],dp[i-1][j])
    else:
      dp[i][j] = min(dp[i][j],dp[i-1][j])
ans = []
for i in range(vmax+1):
  if dp[n][i] <= w:
    ans.append(i)
print(max(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys


def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))


def get_array(): return list(map(int, sys.stdin.readline().strip().split()))

def ks(val, w, W, n, dp):

    if n == 0:
        return 0

    if (n, W) in dp:
        return dp[(n, W)]

    if w[n - 1] > W:
        return ks(val, w, W, n - 1, dp)

    dp[(n, W)] = max(ks(val, w, W - w[n - 1], n - 1, dp) + val[n - 1], ks(val, w, W, n - 1, dp))
    return dp[(n, W)]



n, W = list(map(int, sys.stdin.readline().split()))
val = []
weights = []
for i in range(n):
    w, v = list(map(int, sys.stdin.readline().strip().split()))
    val.append(v)
    weights.append(w)

dp = {}

sys.stdout.write(str(ks(val, weights, W, n, dp)))

Submission status: Time Limit Exceeded

Solution code:
def knapsack(N, C, weights, values):
    dp = [[0 for _ in range(N + 1)] for _ in range(C + 1)]
    for i in range(1, C + 1):
        for j in range(1, N + 1):
            if weights[j - 1] <= i:
                dp[i][j] = max(dp[i][j - 1], values[j - 1] + dp[i - weights[j - 1]][j - 1])
            else:
                dp[i][j] = dp[i][j - 1]
    return dp[C][N]


if __name__ == '__main__':
    n, c = list(map(int, input().split()))
    weights = [0] * n
    values = [0] * n
    for i in range(n):
        weights[i], values[i] = map(int, input().split())
    print(knapsack(n, c, weights, values))

Submission status: Time Limit Exceeded

Solution code:
def knapsack(w,val,W,n,t):
    for i in range(1,n+1):
        for j in range(1,W+1):
            if w[i-1]<=j:
                t[i][j]=max(val[i-1]+t[i-1][j-w[i-1]],t[i-1][j])
            else:
                t[i][j]=t[i-1][j]
    return t[n][W]            
n,W=map(int,input().split())                
w=[]
val=[]
t=[[0 for x in range(W+1)] for x in range(n+1)] 
for i in range(0,n):
    a,b=map(int,input().split())
    w.append(a)
    val.append(b)
ans=knapsack(w,val,W,n,t)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N, W = MI()
inp = LI2(N)
w = [0]+[inp[i][0] for i in range(N)]
v = [0]+[inp[i][1] for i in range(N)]
dp = FILL2(INF,N+1,100001)
dp[0][0] = 0
for i in range(1,N+1):
    for j in range(100001):
        if j-v[i] >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
        else:
            dp[i][j] = dp[i-1][j]
ans = 0
for j in range(100001):
    if dp[N][j] <= W:
        ans = j

print(ans)

Submission status: Time Limit Exceeded

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

v = 0
for i in range(n):
    v += wv[i][1]


dp = [[float('inf') for _ in range(v+1)] for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for j in range(v+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i+1][j],dp[i][j-wv[i][1]]+wv[i][0])
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
ans = 0
for i in range(v+1):
    if dp[n][i] <= w:
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,W= map(int,input().split())
ans=[0 for e in range(W+1)] 
for i in range(N):
 w,v=map(int,input().split())
 for j in range(w,W+1)[::-1]:
  ans[j]=max(ans[j-w]+v,ans[j])
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
N,Max_W = map(int,input().split())
 
dp = [0 for _ in range(Max_W + 1)]
dp = np.array(dp)
 
for i in range(N):
    w,v = map(int,input().split())
    a = dp[:-w] + v
    b = dp[w:]
    m = np.maximum(a,b)
    dp[w:] = m
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_d

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

weights, profits = [], []

for i in range(N):
    w, p = map(int, input().split())
    weights.append(w)
    profits.append(p)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
a= input().split()
N = int(a[0])
W = int(a[1])
wv_list = []
max_value = 0
 
#価値と重さのやつをリストにしてる
for i in range(N):
  b = input().split()
  w = int(b[0])
  v = int(b[1])
  max_value += v
 
  wv_list.append([w, v])
 
#初期化
#とりあえず、全部最大になるように
n_list = [[float('inf') for i in range(max_value + 1)] for j in range(N)]
 
#
n_list[0][wv_list[0][1]] = wv_list[0][0]
 
for i in range(1, N):
 
  for j in range(max_value):
 
    s = j + wv_list[i][1]
 
    if s <= max_value:
      n_list[i][s] = min(n_list[i - 1][j] + wv_list[i][0], n_list[i][s])
    n_list[i][j] = min(n_list[i - 1][j], n_list[i][j])
    n_list[i][wv_list[i][1]] = wv_list[i][0]
 
for i in range(1, max_value):
 
  if n_list[-1][-i] <= W:
    print(max_value - i + 1)
    break

Submission status: Time Limit Exceeded

Solution code:
a= input().split()
N = int(a[0])
W = int(a[1])
wv_list = []
max_value = 0

#価値と重さのやつをリストにしてる
for i in range(N):
  b = input().split()
  w = int(b[0])
  v = int(b[1])
  max_value += v

  wv_list.append([w, v])

#初期化
#とりあえず、全部最大になるように
n_list = [[float('inf') for i in range(max_value + 1)] for j in range(N)]

#
n_list[0][wv_list[0][1]] = wv_list[0][0]

for i in range(1, N):

  for j in range(max_value):

    s = j + wv_list[i][1]

    if s <= max_value:
      n_list[i][s] = min(n_list[i - 1][j] + wv_list[i][0], n_list[i][s])
    n_list[i][j] = min(n_list[i - 1][j], n_list[i][j])
    n_list[i][wv_list[i][1]] = wv_list[i][0]

for i in range(1, max_value):

  if n_list[-1][-i] <= W:
    print(max_value - i + 1)
    break

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split(' '))
w,v=[0]*N,[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split(' '))
dp=[[0]+[W+1]*(sum(v)+1) for _ in range(N+1)]
for i in range(N):
    for nv in range(sum(v),0,-1):
        if nv<v[i]:
            dp[i+1][nv]=min(dp[i][nv],dp[i+1][nv+1])
        else:
            dp[i+1][nv]=min(dp[i][nv],dp[i][nv-v[i]]+w[i])

print(dp[N].index(W+1)-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict as dd
n,w=map(int,input().split())
we=[0]*n
val=[0]*n
for i in range(n):
  ww,v=map(int,input().split())
  we[i]=ww
  val[i]=v
dp=dd(lambda:-1)
def solve(i,w,we,val):
  if(i==0 or w==0):
    return 0
  if(dp[(i,w)]!=-1):
    return dp[(i,w)]
  if(we[i-1]<=w):
    if(dp[(i-1,w-we[i-1])]!=-1):
      x=dp[(i-1,w-we[i-1])]
    else:
      x=dp[(i-1,w-we[i-1])]=solve(i-1,w-we[i-1],we,val)
    if(dp[(i-1,w)]!=-1):
      y=dp[(i-1,w)]
    else:
      y=dp[(i-1,w)]=solve(i-1,w,we,val)
    dp[(i,w)]=max(val[i-1]+x,y)
    return dp[(i,w)]
  else:
    if(dp[(i-1,w)]!=-1):
      y=dp[(i-1,w)]
    else:
      y=dp[(i-1,w)]=solve(i-1,w,we,val)
    dp[(i,w)]=y
    return dp[(i,w)]
print(solve(n,w,we,val))
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
n,w=map(int,input().split())
we=[0]*n
val=[0]*n
for i in range(n):
  ww,v=map(int,input().split())
  we[i]=ww
  val[i]=v
dp=dd(lambda:-1)
def solve(i,w,we,val):
  if(i==0 or w==0):
    return 0
  if(dp[(i,w)]!=-1):
    return dp[(i,w)]
  if(we[i-1]<=w):
    dp[(i,w)]=max(val[i-1]+solve(i-1,w-we[i-1],we,val),solve(i-1,w,we,val))
    return dp[(i,w)]
  else:
    dp[(i,w)]=solve(i-1,w,we,val)
    return dp[(i,w)]
print(solve(n,w,we,val))
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
Value = []
weight = []
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

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


for i in range(N):
  for w in range(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:
l=list(map(int,input().split()))
n=l[0]
w=l[1]
va=[0]*n
wa=[0]*n
for i in range(n):
        
    x=list(map(int,input().split()))
    wa[i]=x[0]
    va[i]=x[1]
dp=[[0 for i in range(w+1)] for j in range(n+1)]
for i in range(1,n+1):
  for j in range(1,w+1):
    if wa[i-1]>j:
      dp[i][j]=dp[i-1][j]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-wa[i-1]]+va[i-1])
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout


def solve(mw, iw, iv):
    vs = sum(iv)
    A = [[float('inf') for i in range(vs+1)] for i in range(len(iv) + 1)]        
    A[0][0] = 0
    for i in range(1, len(iv) + 1):
        for j in range(vs + 1):
            if j < iv[i-1]: A[i][j] = A[i-1][j]
            else: A[i][j] = min(A[i-1][j], A[i-1][j-iv[i-1]] + iw[i-1])
    ans = 0
    for i in range(len(A[0])-1, -1, -1):
        if A[-1][i] != float('inf') and A[-1][i] <= mw:
            return i

# def test():
#     f = open('a.txt', 'r')
#     t = int(f.readline())
#     count, error = 1, 0
#     for _ in range(t):
#         try:
#             n, mw = f.readline().split()
#             iw, iv = [], []
#             for _ in range(int(n)):
#                 w, v = f.readline().split()
#                 iw.append(int(w))
#                 iv.append(int(v))
#             ans = int(f.readline())
#             output = solve(int(mw), iw, iv)
#             if ans != output:
#                 error += 1 
#                 stdout.write(f"Case #:{count} (WA) | Ans: {ans} Output: {output}\n")
#             else:
#                 stdout.write(f"Case #:{count} Pass\n")
#         except RuntimeError:
#             error += 1
#             stdout.write(f"Case #{count} (RE)")
#         count += 1
#     if error == 0: stdout.write("All test cases passed")
#     else: stdout.write(f"Passed: {count-error-1} | Errors: {error}")

def main():
    iw, iv = [], []
    n, mw = [int(i) for i in stdin.readline().split()]
    for _ in range(n):
        w,v = [int(i) for i in stdin.readline().split()]
        iw.append(w)
        iv.append(v)
    print(solve(mw, iw, iv))

main()
# test()

Submission status: Time Limit Exceeded

Solution code:
n,W = map(int,input().split())
w = []
v = []
for _ in range(n):
    weight,value = map(int,input().split())
    w.append(weight)
    v.append(value)

INF = float("inf")
order = 10**5  + 1 
dp = [[INF] * order for _ in range(n+1)] #dp[i+1][value] i番目まで選んで価値をvalue以上にする時の重さの最小値
dp[0][0] = 0

for i in  range(n):
    for value in range(order):
        if value-v[i]>= 0:
            dp[i+1][value] = min(dp[i+1][value],dp[i][value-v[i]] + w[i])
        dp[i+1][value] = min(dp[i+1][value],dp[i][value])

ans = 0
for value in range(order):
    if dp[n][value] <= W:
        ans = max(ans,value)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
def main():
    N, W = map(int, input().split())
    V = 10**3 * 100
    
    f_inf = float("inf")
    dp = [f_inf] * (V+1)
    dp[0] = 0
    
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(V-v, -1, -1):
            if dp[i] == -1:
                continue
            dp[i+v] = min(dp[i+v], dp[i] + w)

    # print(dp)
    ans = 0
    for i in range(len(dp)):
        if dp[i] <= W and i >= ans:
            ans = i

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
def main():
    N, W = map(int, input().split())
    V = 10**3 * 100
    
    dp = [[float("inf")]*(V) for _ in range(N+1)]
    dp[0][0] = 0
    
    for i in range(1, N+1):
        w, v = map(int, input().split())
        for j in range(V):
            if j-v >= 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j-v]+w)
            dp[i][j] = min(dp[i][j], dp[i-1][j])
        
    ans = 0
    for i in range(len(dp[N])):
        if dp[N][i] > W:
            continue
        if i >= ans:
            ans = i
            
    # print(dp)
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

weights, values = [], []
valuesum = 0
for _ in range(n):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)
    valuesum += v

# N*W = 100*10**9 = 10**11. We are looking for minimum weight so initializaiton should be large numbers.
# in D , dp was looking for maximum value so intialization was all 0s.

dp = [10**11 + 1]*(valuesum + 1)
dp[0] = 0   # no items for 0 value

for item in range(n):
    w, v = weights[item], values[item]
    for value in range(valuesum - v, -1, -1):
        dp[value + v] = min(dp[value + v], dp[value] + w)

for i in range(valuesum, -1, -1):
    if dp[i] <= W:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def knapsack(n,w):
    global weight,value,bag
    if(n==0 or w== 0):
        return 0
    temp=str(n)+' '+str(w)
    if(temp in bag):
        return bag[temp]
    if(weight[n-1]<=w):
        bag[temp]=max(value[n-1]+knapsack(n-1,w-weight[n-1]),knapsack(n-1,w))
        return bag[temp]
    else:
        bag[temp]=knapsack(n-1,w)
        return bag[temp]
n,w=map(int,input().split())
value=[]
weight=[]
bag=dict()
for _ in range(n):
    tempw,tempv=map(int,input().split())
    value.append(tempv)
    weight.append(tempw)
print(knapsack(n,w))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
inf = int(1e20)
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(" ".join(map(str, var))+end)
def l(): return list(sp())
def sp(): return map(int, data().split())


n, weight = sp()
mat = []
for i in range(n):
    mat.append(l())
dp = dd(lambda: dd(lambda: inf))
dp[n-1][0] = 0
dp[n-1][mat[n-1][1]] = mat[n-1][0]
for i in range(n-2, -1, -1):
    for j in range(100001):
        dp[i][j] = dp[i+1][j]
        if mat[i][1] <= j:
            dp[i][j] = min(dp[i][j], dp[i+1][j-mat[i][1]] + mat[i][0])
for i in range(100000, -1, -1):
    if dp[0][i] <= weight:
        out(i)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import array
n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
t=[[0 for i in range(n+1)] for j in range(w+1)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(weight[j-1]<=i):
            t[i][j]=max(value[j-1]+t[i-weight[j-1]][j-1],t[i][j-1])
        else:
            t[i][j]=t[i][j-1]
print(t[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify

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

dp = [{0: 0}] + [{} for i in range(N)]

for i in range(1, N+1):
  w, v = wv[i]
  for mw, mv in dp[i-1].items():
    dp[i][mw] = max(dp[i].get(mw, 0), dp[i-1].get(mw, 0))
    if mw + w < W+1:
      dp[i][mw+w] = max(dp[i].get(mw+w, 0), dp[i-1][mw]+v, dp[i-1].get(mw+w, 0))

print(max(dp[N].values()))

Submission status: Time Limit Exceeded

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

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

dp = [{0: 0}] + [{} for i in range(N)]

for i in range(1, N+1):
  w, v = wv[i]
  for mw, mv in dp[i-1].items():
    dp[i][mw] = max(dp[i].get(mw, 0), dp[i-1].get(mw, 0))
    if mw + w < W+1:
      dp[i][mw+w] = max(dp[i].get(mw+w, 0), dp[i-1][mw]+v, dp[i-1].get(mw+w, 0))

print(max(dp[N].values()))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
w=np.array(w)
v=np.array(v)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=np.array([np.array([float("inf") for i in range(maxV*(N+1))]) for j in range(N+1)])
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
w=np.array(w)
v=np.array(v)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)