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 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())
    w=[0]*(n+1)
    v=[0]*(n+1)
    for i in range(1,n+1):
        w[i],v[i]=map(int,input().split())
    dp=[[-1]*(W+1) for _ in range(n+1)]

    def solve(i,x): # i番目の時点で残り容量x
        if(x<0): return -INF
        if(i>n): return 0
        if(dp[i][x]!=-1): return dp[i][x]
        dp[i][x]=max(solve(i+1,x),solve(i+1,x-w[i])+v[i])
        return dp[i][x]

    print(solve(1,W))
resolve()

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())
    w=[0]*(n+1)
    v=[0]*(n+1)
    for i in range(1,n+1):
        w[i],v[i]=map(int,input().split())

    def solve(i,x): # i番目の時点で残り容量x
        if(x<0): return -INF
        if(i>n): return 0
        return max(solve(i+1,x),solve(i+1,x-w[i])+v[i])

    print(solve(1,W))
resolve()

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())
    w=[0]*(n+1)
    v=[0]*(n+1)
    for i in range(1,n+1):
        w[i],v[i]=map(int,input().split())

    def solve(i,W):
        if(i>n): return 0
        res=0
        if(W>=w[i]): res=solve(i+1,W-w[i])+v[i]
        res=max(res,solve(i+1,W))
        return res

    print(solve(1,W))
resolve()

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 = [[0 for i in range(W+1)] for j in range(N+1)]

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

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

Submission status: Time Limit Exceeded

Solution code:

n,w=map(int,input().split())

l=[]
for i in range(n):
    x,y=map(int,input().split())
    l.append((x,y))
#l.sort()
p=[[0 for i in range(w+1)] for j in range(n+1)]

for i in range(n+1):
    for j in range(w+1):
        if i==0 or w==0:
            p[i][w]=0
        elif l[i-1][0]<=j:
           # print(j)
            k=max(l[i-1][1]+p[i-1][j-l[i-1][0]],p[i-1][j])
            p[i][j]=k
        else:
            p[i][j]=p[i-1][j]
print(p[n][w])

Submission status: Time Limit Exceeded

Solution code:

n,w=map(int,input().split())

l=[]
for i in range(n):
    x,y=map(int,input().split())
    l.append((x,y))
l.sort()
p=[[0 for i in range(w+1)] for j in range(n+1)]

for i in range(n+1):
    for j in range(w+1):
        if i==0 or w==0:
            p[i][w]=0
        elif l[i-1][0]<=j:
           # print(j)
            k=max(l[i-1][1]+p[i-1][j-l[i-1][0]],p[i-1][j])
            p[i][j]=k
        else:
            p[i][j]=p[i-1][j]
print(p[n][w])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
n, m = 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] * (m + 1) for _ in range(n + 1)]


def rec(i, j):
    res = 0
    if dp[i][j] >= 0:
        return dp[i][j]
    if i == n:
        res = 0
    elif j < w[i]:
        res = rec(i + 1, j)
    else:
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i])
    return res


print(rec(0, m))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
n, m = 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] * (m + 1) for _ in range(n + 1)]


def rec(i, j):
    res = 0
    if dp[i][j] >= 0:
        return dp[i][j]
    if i == n:
        res = 0
    elif j < w[i]:
        res = rec(i + 1, j)
    else:
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i])
    dp[i][j] = res
    return res


print(rec(0, m))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
n, m = 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] * (m + 1) for _ in range(n + 1)]


def rec(i, j):
    res = 0
    if dp[i][j] >= 0:
        return dp[i][j]
    if i == n:
        res = 0
    elif j < w[i]:
        res = rec(i + 1, j)
    else:
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i])
    dp[i][j] = res
    return dp[i][j]


print(rec(0, m))

Submission status: Time Limit Exceeded

Solution code:
#19:00
n, wm = [int(x) for x in input().strip().split()]
w = []
v = []
for i in range(n):
    wi, vi = [int(x) for x in input().strip().split()]
    w.append(wi)
    v.append(vi)

dp = [[None for i in range(wm+1)] for j in range(n)]

def solve(i,j):
    if dp[i][j]:
        return dp[i][j]
    if i<0:
        return 0
    else:
        if j>=w[i]:
            dp[i][j] = max(solve(i-1,j), solve(i-1,j-w[i])+v[i])
        else:
            dp[i][j] = solve(i-1,j)

    return dp[i][j]

print(solve(n-1,wm))
# print(dp)

Submission status: Time Limit Exceeded

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

dp=[0]*(W+1)

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

     for weight in range(W-w,-1,-1):
          dp[weight+w] =  max( dp[weight+w] , dp[weight]+v)

print(max(dp))

Submission status: Time Limit Exceeded

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


dp[0][0]=0

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

for weight in range(W+1):
     for element in range(1,N):
          if weights[element]<=weight:
               dp[element][weight]= max(dp[element-1][weight],values[element]+dp[element-1][weight-weights[element]])
          else:
               dp[element][weight]=dp[element-1][weight]


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

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(100000)

class Solver(object):
    def __init__(self,N:int,W:int,values:list,weights:list):
        self.N = N   ## MAX number of item
        self.values = values  ## list of item value
        self.weights = weights ## list of item weight
        self.dp = [[None]*(W+1) for _ in range(N+1)] ## memorize the result

    ## i番目以降から重さがj以下になるように選ぶ時に価値が最大になるようにする。
    def solve(self,i:int,j:int) -> int:
        if self.dp[i][j] != None:
            return self.dp[i][j]
        if i == self.N:
            res = 0
        elif j < self.weights[i]:
            res = self.solve(i+1,j)
        else:
            res = max(self.solve(i+1,j),self.solve(i+1,j-self.weights[i])+self.values[i])
        self.dp[i][j] = res
        return res

def main():
    N,W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    weights = [item[0] for item in items]
    values = [item[1] for item in items]
    solver = Solver(N,W,values,weights)
    ans = solver.solve(0,W)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)

class Solver(object):
    def __init__(self,N:int,W:int,values:list,weights:list):
        self.N = N   ## MAX number of item
        self.values = values  ## list of item value
        self.weights = weights ## list of item weight
        self.dp = [[None for _ in range(W+1)] for _ in range(N+1)] ## memorize the result

    ## i番目以降から重さがj以下になるように選ぶ時に価値が最大になるようにする。
    def solve(self,i:int,j:int) -> int:
        if self.dp[i][j] != None:
            return self.dp[i][j]
        if i == self.N:
            res = 0
        elif j < self.weights[i]:
            res = self.solve(i+1,j)
        else:
            res = max(self.solve(i+1,j),self.solve(i+1,j-self.weights[i])+self.values[i])
        self.dp[i][j] = res
        return res

def main():
    N,W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    weights = [item[0] for item in items]
    values = [item[1] for item in items]
    solver = Solver(N,W,values,weights)
    ans = solver.solve(0,W)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import bisect

def knapsack(N,W,w,v):
    dp=[[0 for i in range(W+1)]for j in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
            next_w=j+w[i]
            next_v=dp[i][j]+v[i]
            if(next_w<=W and next_v>dp[i+1][next_w]):
                dp[i+1][next_w]=next_v
    ans = 0
    for i in range(W+1):
        ans=max(ans,dp[N][i])
    return(ans)

N,W = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(N)]

v = []
w = []

for i in range(N):
    v.append(li[i][0])
    w.append(li[i][1])

print(knapsack(N,W,v,w))

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
#input
n,w = map(int,input().split())
object = [list(map(int,input().split())) for _ in range(n)]

#initialization
dp = [[0 for _ in range(100100)] for _ in range(110)]

#dp algorithm
for i in range(n):
  for sum_w in range(w+1):
    #add value
    if sum_w - object[i][0] >= 0:
      dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - object[i][0]] + object[i][1]);
    #not add value
    dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w]);

#output
print(dp[n][w])

Submission status: Time Limit Exceeded

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

vw = [0] * (mw + 1)

for i in range(n):
  for j in reversed(range(iwv[i][0], mw + 1)):
    vw[j] = max(vw[j], vw[j - iwv[i][0]] + iwv[i][1])
  
print(max(vw))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main(n, w, items):
    dp = np.zeros((n + 1, w + 1), dtype=int)
    for i in range(1, n + 1):
        weight, value = items[i - 1]
        for j in range(weight):
            dp[i][j] = dp[i - 1][j]
        for j in range(weight, w + 1):
            added = dp[i - 1][j - weight] + value
            not_added = dp[i - 1][j]
            dp[i][j] = max(added, not_added)
    return dp[n][w]


if __name__ == '__main__':
    N, W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))
    print(main(N, W, I))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, W = (int(i) for i in input().split())
    weight = [0] * (N+1)
    value = [0] * (N+1)
    for i in range(1, N+1):
        w, v = (int(i) for i in input().split())
        weight[i] = w
        value[i] = v
    memo = [[-1] * (W + 1) for _ in range(N + 1)]

    def rec(i, w):
        if i == 0:
            return 0
        if memo[i][w] != -1:
            return memo[i][w]
        res = 0
        if w - weight[i] >= 0:
            res = max(rec(i-1, w), rec(i-1, w-weight[i])+value[i])
        else:
            res = rec(i-1, w)
        memo[i][w] = res
        return res

    print(rec(N, W))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, W = (int(i) for i in input().split())
    weight = [0] * (N+1)
    value = [0] * (N+1)
    for i in range(1, N+1):
        w, v = (int(i) for i in input().split())
        weight[i] = w
        value[i] = v
    memo = [[-1 for i in range(W + 1)] for j in range(N + 1)]

    def rec(i, w):
        if i == 0:
            return 0
        if memo[i][w] != -1:
            return memo[i][w]
        res = 0
        if w - weight[i] >= 0:
            res = max(rec(i-1, w), rec(i-1, w-weight[i])+value[i])
        else:
            res = rec(i-1, w)
        memo[i][w] = res
        return res

    print(rec(N, W))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
d,f=map(int,input().split())
if n==1:print(f if d<=w else 0);exit()
dp=[[0,0],[d,f]]#w,v
dp_=[]
for i in range(1,n):
  d,f=map(int,input().split())
  if dp_==[]:
    for x,c in dp:
      if x+d<=w:dp_.append([x+d,c+f])
    dp_+=dp
    dp=[]
  else:
    for x,c in dp_:
      if x+d<=w:dp.append([x+d,c+f])
    dp+=dp_
    dp_=[]
print(max(sum(dp+dp_,[])[1::2]))

Submission status: Time Limit Exceeded

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

for i in range(n):
    temp1, temp2 = map(int, input().split())
    w.append(temp1)
    v.append(temp2)

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

dp = [[None for i in range(W+1)] for j in range(n+1)]
#dp[0][0] = 0

#print(dp)

def solve(total, i):
    if dp[i][total] is not None:
        return dp[i][total]

    if i > n-1:
        return 0
    if total > W:
        return 0

    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(total + weight, i+1)
        unchose = solve(total, i+1)
        dp[i][total] = max(chose, unchose)
        return dp[i][total]
    else:
        dp[i][total] = solve(total, i+1)
        return dp[i][total]


print(solve(0, 0))

Submission status: Time Limit Exceeded

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

for i in range(n):
    temp1, temp2 = map(int, input().split())
    w.append(temp1)
    v.append(temp2)

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

dp = [[None for i in range(W+1)] for j in range(n+1)]
#dp[0][0] = 0

#print(dp)

def solve(total, i):
    if dp[i][total] is not None:
        return dp[i][total]

    if i > n-1:
        return 0

    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(total + weight, i+1)
        unchose = solve(total, i+1)
        dp[i][total] = max(chose, unchose)
        return dp[i][total]
    else:
        dp[i][total] = solve(total, i+1)
        return dp[i][total]


print(solve(0, 0))

Submission status: Time Limit Exceeded

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

for i in range(n):
    temp1, temp2 = map(int, input().split())
    w.append(temp1)
    v.append(temp2)

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

dp = [[None for i in range(W+1)] for j in range(n+1)]
#dp[0][0] = 0

#print(dp)

def solve(total, i):
    if i > n-1:
        #return dp[total][i-1]
        return 0

    if dp[i][total] is not None:
        return dp[i][total]

    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(total + weight, i+1)
        unchose = solve(total, i+1)
        dp[i][total] = max(chose, unchose)
        return dp[i][total]
    else:
        dp[i][total] = solve(total, i+1)
        return dp[i][total]
        # if i < n-1:
        #     return solve(total, i+1)
        # else:
        #     return v[i-1]


print(solve(0, 0))

Submission status: Time Limit Exceeded

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

for i in range(n):
    temp1, temp2 = map(int, input().split())
    w.append(temp1)
    v.append(temp2)

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

dp = [[None for i in range(W+1)] for j in range(n+1)]
#dp[0][0] = 0

#print(dp)

def solve(total, i):
    if i > n-1:
        #return dp[total][i-1]
        return 0

    if dp[i][total] is not None:
        return dp[i][total]

    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(total + weight, i+1)
        unchose = solve(total, i+1)
        dp[i][total] = max(chose, unchose)
        return dp[i][total]
    else:
        return solve(total, i+1)
        # if i < n-1:
        #     return solve(total, i+1)
        # else:
        #     return v[i-1]


print(solve(0, 0))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

dp = [0]*(W+1)
for i in range(N):
	w, v = map(int, input().split())
	for j in range(W, w-1, -1):
		dp[j] = max(dp[j], dp[j-w] + v)
print(dp[-1])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
bag = [0 for _ in range(W+1)]
for w,v in a:
  for i in range(min(w,W+1),W+1)[::-1]:
    bag[i] = max(bag[i], bag[i-w] + v)
print(bag[W])

Submission status: Time Limit Exceeded

Solution code:
n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
bag = [0 for _ in range(W+1)]
for w,v in a:
  for i in range(w,W+1)[::-1]:
    bag[i] = max(bag[i], bag[i-w] + v)
print(bag[W])

Submission status: Time Limit Exceeded

Solution code:
"""
ナップサック問題
"""
N,W = map(int, input().split())
dp = [[-1 for i in range(100100)] for j in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if dp[i][j] == -1:
            continue
        elif j+w <= W:
            # print("i:{},j:{},value1:{}".format(i,i+j,max(dp[i][j]+v, dp[i][j+w])))
            dp[i+1][j+w] = max(dp[i][j]+v, dp[i][j+w])
            # print(dp[i+1][j+w],i+1,j+w)
 
print(max(dp[N][:W+1]))

Submission status: Time Limit Exceeded

Solution code:
import sys

n,w = map(int, sys.stdin.readline().strip().split(' '))
arr = []
for _ in range(n):
    wi, vi = map(int, sys.stdin.readline().strip().split(' '))
    arr.append((wi, vi))

dp = [-1 for i in range(w+1)]
t = [-1 for j in range(w+1)]
for i in range(n):
    for j in range(1, w+1):
        if j-arr[i][0] >= 1 and dp[j-arr[i][0]] != -1:
            # print(j, j-arr[i][0], t[j], dp[j-arr[i][0]]+arr[i][1], dp[j-arr[i][0]])
            t[j] = max(t[j], dp[j-arr[i][0]]+arr[i][1])
    t[arr[i][0]] = max(t[arr[i][0]], arr[i][1])

    for j in range(1, w+1):
        dp[j] = max(dp[j], t[j])
        t[j] = -1
# print(dp)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys

n,w = map(int, sys.stdin.readline().strip().split(' '))
arr = []
for _ in range(n):
    wi, vi = map(int, sys.stdin.readline().strip().split(' '))
    arr.append((wi, vi))

dp = [-1 for i in range(w+1)]
# for i in range(n):
#     dp[arr[i][0]] = max(dp[arr[i][0]], arr[i][1])
for i in range(n):
    t = [-1 for j in range(w+1)]
    for j in range(1, w+1):
        if j-arr[i][0] >= 1 and dp[j-arr[i][0]] != -1:
            # print(j, j-arr[i][0], t[j], dp[j-arr[i][0]]+arr[i][1], dp[j-arr[i][0]])
            t[j] = max(t[j], dp[j-arr[i][0]]+arr[i][1])
    t[arr[i][0]] = max(t[arr[i][0]], arr[i][1])

    for j in range(1, w+1):
        dp[j] = max(dp[j], t[j])
# print(dp)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import copy

N, W = list(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] = list(map(int, input().split()))


# N, W = [3, 8]
# w = [0 for i in range(N)]
# v = [0 for i in range(N)]


# w[0], v[0] = [3, 30]
# w[1], v[1] = [4, 50]
# w[2], v[2] = [5, 60]

s = [0 for i in range(W+1)]


for i in range(N):
    #print(s)
    ns = copy.copy(s)
    for j in range(W+1):
        for k in range(j + w[i], W+1):
            ns[k] = max(s[k], s[j] + v[i])
    s = ns

print(max(s))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

dp=[-1]*(W+1)
dp[0]=0

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W=map(int,input().split())
weight=np.zeros(N,np.int64)
values=np.zeros(N,np.int64)
for i in range(N):
  weight[i],values[i]=map(int,input().split())

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

for i in range(N):
  for w in range(W+1):
    if w>=weight[i]:
      dp[i+1][w]=max(dp[i][w],dp[i][w-weight[i]]+values[i])
    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())
weight=[0]*N
values=[0]*N
for i in range(N):
  weight[i],values[i]=map(int,input().split())

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

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

Submission status: Time Limit Exceeded

Solution code:
N,W = 102,10**5+3
weight,value = [None for _ in range(W)],[None for _ in range(N)]
n,w = None,None

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

def solve(n,w):
    global dp
    # print("in {} ".format(n))
    if w < 0:
        return float('-inf')
    elif n < 0:
        return 0
    elif dp[n][w] != -1:
        return dp[n][w]
    dp[n][w] = max(value[n] + solve(n-1,w-weight[n]),solve(n-1,w))
    return dp[n][w]

def main():
    global n
    global w
    n,w = map(int,input().strip().split())
    for _ in range(n):
        weight[_],value[_] = map(int,input().strip().split())
    print(solve(n-1,w))

main()

Submission status: Time Limit Exceeded

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

def main():
    N,W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))

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

    ans = 0
    for a in dp:
        ans = max(ans, max(a))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

def main():
    N,W = map(int, input().split())
    w = []
    v = []
    for _ in range(N):
        x,y = map(int, input().split())
        w.append(x)
        v.append(y)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
def knapsack(val,wt,n,k):
    b = [[0 for _ in range(k+1)]for _ in range(n+1)]
    for i in range(n+1):
        for j in range(k+1):
            if j==0 or i==0:
                b[i][j] = 0
            elif wt[i-1]<=j:
                b[i][j] = max(val[i-1]+b[i-1][j-wt[i-1]],b[i-1][j])
            else:
                b[i][j] = b[i-1][j]
    return b[n][k]
from sys import stdin
input = stdin.readline
n,k = list(map(int,input().split()))
val,wt = [],[]
for _ in range(n):
    x,y = list(map(int,input().split()))
    val.append(y)
    wt.append(x)
p = knapsack(val,wt,n,k)
print(p)

Submission status: Time Limit Exceeded

Solution code:
# import copy
import sys
import numpy as np
imput = sys.stdin.readline
def main():
    N, W = map(int, input().split())
    dp = np.zeros((N+1, W+1))
    for i in range(1, N+1):
        w, v = map(int, input().split())
        for j in range(1, W+1):
            if j<w:
                dp[i, j] = dp[i-1, j]
            else:
                dp[i, j] = max(dp[i-1, j], dp[i-1, j-w]+v)
    # print(dp)
    print(int(dp[i, j]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,W = (int(i) for i in input().split())
weights = []
values = []
for j in range(n):
    wt, val = [int(i) for i in input().split()]
    weights.append(wt)
    values.append(val)

prevdp = [0]*(W+1)
tempdp = [0]*(W+1)

for i in range(1,n+1):
    wI = weights[i-1]
    vI = values[i-1]
    
    for j in range(1,W+1):
        if wI>j:
            tempdp[j] = prevdp[j]
        else:
            tempdp[j] = max(prevdp[j],vI+prevdp[j-wI])
    prevdp = tempdp[:]

print(prevdp[-1])

Submission status: Time Limit Exceeded

Solution code:
n,W = (int(i) for i in input().split())
weights = []
values = []
for j in range(n):
    wt, val = [int(i) for i in input().split()]
    weights.append(wt)
    values.append(val)

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

for i in range(1,n+1):
    wI = weights[i-1]
    vI = values[i-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[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
n,w = (int(i) for i in input().split())
allItems = [[int(i) for i in input().split()] for j in range(n)]
##weight,value
allItems.sort(key = lambda x:x[0])
allItems.sort(key = lambda x:-x[1])
##print(allItems)
##print()
def getMaxSum(items,emptyWt):
    if emptyWt==0:
        return 0
    if emptyWt==1:
        for i in items:
            if i[0]==1:
                return i[1]
        return 0
    prevWt = {}
    maxRes = -1
    for i in range(len(items)):
        wt,val = items[i]
        if (wt in prevWt) or wt>emptyWt:
            continue
        prevWt[wt]=0
        res = val+getMaxSum(items[:i]+items[i+1:],emptyWt-wt)
        if res>maxRes:
            maxRes = res
    return maxRes
        
prevWt = {}
maxRes = -1
for i in range(n):
    wt,val = allItems[i]
    if wt in prevWt:
        continue
    prevWt[wt]=0
    res = val+getMaxSum(allItems[:i]+allItems[i+1:],w-wt)
    if res>maxRes:
        maxRes = res
print(maxRes)

Submission status: Time Limit Exceeded

Solution code:
n,w = (int(i) for i in input().split())
allItems = [[int(i) for i in input().split()] for j in range(n)]

allItems.sort(key = lambda x:x[0])
allItems.sort(key = lambda x:-x[1])

def getMaxSum(items,emptyWt):
    if emptyWt==0:
        return 0
    if emptyWt==1:
        for i in items:
            if i[0]==1:
                return i[1]
        return 0
    prevWt = {}
    maxRes = -1
    for i in range(len(items)):
        wt,val = items[i]
        if (wt in prevWt) or wt>emptyWt:
            continue
        prevWt[wt]=0
        res = val+getMaxSum(items[:i]+items[i+1:],emptyWt-wt)
        if res>maxRes:
            maxRes = res
    return maxRes
        
prevWt = {}
maxRes = -1
for i in range(n):
    wt,val = allItems[i]
    if wt in prevWt:
        continue
    prevWt[wt]=0
    res = val+getMaxSum(allItems[:i]+allItems[i+1:],w-wt)
    if res>maxRes:
        maxRes = res
print(maxRes)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,w = [int(i) for i in input().split()]
arr = []
for i in range(n):
    arr.append([int(i) for i in input().split()])

dp = [[-1 for i in range(n+2)] for i in range(w+1)]

def cal(i,w):

    if i==len(arr) and w>=0:
        return 0
    if i>=len(arr):
        return -1000000000
    
    if w<0:
        return -1000000000
    if w==0:
        return 0
    
    elif dp[w][i]==-1:
        dp[w][i] = max(arr[i][1] + cal(i+1,w-arr[i][0]) , cal(i+1, w))
    return dp[w][i]

    
print(max(0,cal(0,w)))