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:
from sys import stdin

if __name__ == "__main__":
    N, W = [int(i) for i in input().split()]
    weights = []
    values = []
    for i in range(N):
        w, v = [int(i) for i in input().split()]
        weights.append(w)
        values.append(v)
    
    dp = [[0]*(W+1) for i in range(N+1)]
    
    for n in range(0, N):
        for w in range(0, W+1):
            if w-weights[n] >= 0:
                dp[n+1][w] = max(dp[n][w], dp[n][w-weights[n]] + values[n])
            else:
                dp[n+1][w] = dp[n][w]
    
    print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
n, ww = map(int, input().split())
dp = np.zeros([n, ww+1], dtype='int64')
w, v = map(int, input().split())
dp[0] = np.array([v if i >= w else 0 for i in range(ww+1)])
def knapsack(n, ww):
  for i in range(1, n):
    w, v = map(int, input().split())
    for j in range(1,ww+1):
      if j+w <= ww:
        dp[i][j+w] = np.maximum(dp[i-1][j+w], dp[i-1][j]+v)
      dp[i][j] = np.maximum(dp[i-1][j],dp[i][j])
  return dp[-1][-1]

print(knapsack(n, ww))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
n, ww = map(int, input().split())
dp = np.zeros([n, ww+1], dtype='int64')
w, v = map(int, input().split())
dp[0] = np.array([v if i >= w else 0 for i in range(ww+1)])
for i in range(1, n):
  w, v = map(int, input().split())
  for j in range(1,ww+1):
    if j+w <= ww:
      dp[i][j+w] = np.maximum(dp[i-1][j+w], dp[i-1][j]+v)
    dp[i][j] = np.maximum(dp[i-1][j],dp[i][j])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
n, ww = map(int, input().split())

dp = np.array([[0 for _ in range(ww+1)] for _ in range(n)])
w, v = map(int, input().split())
dp[0] = np.array([v if i >= w else 0 for i in range(ww+1)])
for i in range(1, n):
  w, v = map(int, input().split())
  for j in range(1,ww+1):
    if j+w <= ww:
      dp[i][j+w] = max(dp[i-1][j+w], dp[i-1][j]+v)
    dp[i][j] = max(dp[i-1][j],dp[i][j])

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

Submission status: Time Limit Exceeded

Solution code:
import copy
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
dp=([0]*wv[0][0])+[wv[0][1]]*(w+1-wv[0][0])
for i in range(n-1):
    dp_copy=copy.deepcopy(dp)
    for j in range(w+1):
        if j>=wv[i+1][0]:
            dp[j]=max(dp_copy[j],dp_copy[j-wv[i+1][0]]+wv[i+1][1])
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import os
import operator
import sys
from io import BytesIO, IOBase

def inar():
    return [int(k) for k in input().split()]
def main():
    n,we=map(int,input().split())
    arr=[]
    for i in range(n):
        w,v=inar()
        arr.append([w,v])
    arr.sort()
    dp=[]
# ?print(arr)
    for i in range(n+1):
        lis=[0]*(we+1)
        dp.append(lis)
    # for i in range(n+1):
    #     print(*dp[i])
    for i in range(1,n+1):
        for j in range(1,we+1):
            if arr[i-1][0]>j:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(dp[i-1][j],arr[i-1][1]+dp[i-1][j-arr[i-1][0]])
    # for i in range(n+1):
    #     print(*dp[i])
    print(dp[n][we])








BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    import numpy as np

    readline = sys.stdin.readline

    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for _ in [0] * N]
    
    dp = np.zeros((N, W + 1), np.int64)

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


resolve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

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

    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(W,-1,-1):# 後ろから更新しないとダメ
            if j - w >= 0:
                dp[j] = max(dp[j], dp[j-w]+v)
    print(dp[W])    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, W = map(int, input().split())
    w = [None] * N
    v = [None] * N

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def knapsack_1():
    n, w = list(map(int, input().split()))
    items = []
    for _ in range(n):
        items.append(list(map(int, input().split())))
    def helper(pos, t_w):
        if t_w >= w:
            return 0
        maxi = 0
        for i in range(pos+1, len(items)):
            if t_w + items[i][0] <= w:
                maxi = max(maxi, items[i][1] + helper(i, t_w + items[i][0]))
        return maxi
    print(helper(-1, 0))

knapsack_1()

Submission status: Time Limit Exceeded

Solution code:
N,capacity = map(int,input().split(" "))
baggage = []
for i in range(N):
  baggage.append([int(x) for x in input().split(" ")])
dp = [0]*(capacity+1)
for i in range(N):
  for j in range(capacity-baggage[i][0]+1):
    dp[-(j+1)] = max(dp[-(j+1)],dp[-(j+baggage[i][0]+1)]+baggage[i][1])

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))
 
Sum_Weight = sum(map(lambda x:x[0],Goods_List))
dp = [[-1] * (W + 1) for i in range(N)]
 
for i in range(N):
    Current_Weight = Goods_List[i][0]
    Current_Value  = Goods_List[i][1]
    dp[i][0] = 0
    if (i == 0) & (Current_Weight <= W) :
        dp[i][Current_Weight] = Current_Value
    elif i > 0:
        Last_Search_List = [j for j, x in enumerate(dp[i-1]) if x > -1]
        Current_Search_List = list(map(lambda x:x+Current_Weight,Last_Search_List))
        ##まずは前回値を入れる
        for l in range(len(Last_Search_List)):
            Last_Search_Weight =  Last_Search_List[l] 
            dp[i][Last_Search_Weight] = dp[i-1][Last_Search_Weight]
        ##今回値と比べる
        for k in range(len(Current_Search_List)):
            Last_Search_Weight =  Last_Search_List[k] 
            Current_Search_Weight = Current_Search_List[k]
            if Current_Search_Weight > W:
                break
            else:
                dp[i][Current_Search_Weight] = max((dp[i-1][Last_Search_Weight] + Current_Value),
                                                   dp[i-1][Current_Search_Weight])
 
 
print(max(dp[N-1]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

DP= [[0]*100010  for i in range(110)]
def chmax(a,b):
    if a>b:
        return a
    else:
        return b


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


for i in range(N):
    for j in range(W+1):
        if j-S[i][0]>=0:
            
            DP[i+1][j]=chmax(DP[i][j],DP[i][j-S[i][0]]+S[i][1])
        
        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())  # 個数、重さの総和
array = [list(map(int, input().split())) for _ in range(N)]  # [重さ、価値]

# dp[i][w] 各重さの時の価値の最大値
dp = [[0] * W for _ in range(N)]

for i in range(N):
    for w in range(W):  # 1〜Wまでの重さの時の価値の最大値を算出
        if i == 0:
            if array[i][0] <= w + 1:
                dp[i][w] = array[i][1]
        else:
            for j in range(W):
                weight = j + array[i][0]
                value = dp[i - 1][j] + array[i][1]
                # 一つ前の価値を初期値として設定
                if dp[i][w] == 0:
                    dp[i][w] = dp[i - 1][w]
                # 重さの範囲内での価値の最大値を設定
                if weight <= w and dp[i][w] < value:
                    dp[i][w] = value
print(max(dp[N - 1]))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
"""
https://atcoder.jp/contests/dp/tasks/dp_d
"""
import sys

N,W = [int(i) for i in sys.stdin.readline().split(" ")]
wt = []
val = []
for i in range(N):
    w, v = [int(i) for i in sys.stdin.readline().split(" ")]
    wt.append(w)
    val.append(v)
    
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 wt[i-1] <= j:
            dp[i][j] = max(
                val[i-1] + dp[i-1][j-wt[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:
"""
https://atcoder.jp/contests/dp/tasks/dp_d
"""
import sys

N,W = [int(i) for i in sys.stdin.readline().split(" ")]
wt = []
val = []
for i in range(N):
    w, v = [int(i) for i in sys.stdin.readline().split(" ")]
    wt.append(w)
    val.append(v)
    
dp = [[0 for i in range(sum(wt) + 1)] for j in range(N+1)] 

for i in range(1, N + 1):
    for j in range(1, sum(wt) + 1):
        if wt[i-1] <= j:
            dp[i][j] = max(
                val[i-1] + dp[i-1][j-wt[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
input = sys.stdin.readline
n,w = map(int,input().split())
wv = [tuple(map(int,input().split())) for i in range(n)]

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

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
masukan = input()
masukan = masukan.split()
n = int(masukan[0])
k = int(masukan[1])

W = []
V = []
for _ in range(n):
  masukan = input()
  masukan = masukan.split()
  W.append(int(masukan[0]))
  V.append(int(masukan[1]))

def knapsack1(pos, curr_weight):
    if pos == len(W):
        return 0
    
    if curr_weight - W[pos] >= 0:
        return max(knapsack1(pos+1, curr_weight-W[pos])+V[pos], knapsack1(pos+1, curr_weight))
    else:
        return knapsack1(pos+1, curr_weight)
      
print(knapsack1(0, k))

Submission status: Time Limit Exceeded

Solution code:
def knapsack1(pos, curr_weight):
    if pos == len(W):
        return 0
    if curr_weight - W[pos] >= 0:
        return max(knapsack1(pos + 1, curr_weight - W[pos]) + V[pos], knapsack1(pos + 1, curr_weight))
    else:
        return knapsack1(pos + 1, curr_weight)
 
 
if __name__ == '__main__':
    # N W
    NW = input().rstrip().split()
    n = int(NW[0])
    w = int(NW[1])
 
    W = []
    V = []
 
    for _ in range(n):
        inp = input().rstrip().split()
        W.append(int(inp[0]))
        V.append(int(inp[1]))
 
    print(knapsack1(0, w))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = [int(x) for x in input().split()]
weight = np.zeros((N,2))
for x in range(N):
    weight[x] = [int(y) for y in input().split()]
#topdown
memo = np.zeros((N+1,W+1))
for x in range(N+1):
    memo[x] = [-1]*(W+1)

def dp(n,w):
    if w < 0:
        return -float('inf')
    elif n == 0 or w == 0:
        return 0
    elif memo[n][w] != -1:
        return memo[n][w]
    else:
        memo[n][w] = max(dp(n-1,w), dp(n-1,w - int(weight[n-1][0])) + weight[n-1][1])
        return memo[n][w]

print(int(dp(N,W)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, w = map(int, input().split())
a = np.zeros((n, 2))
for i in range(n):
    a[i] = [int(x) for x in input().split()]
memo = np.zeros((n+1, w+1))
ans = 0
for i in range(1, n + 1):
    for j in range(0, w+1):
        memo[i][j] = max(memo[i][j], memo[i-1][j])
    for j in reversed(range(int(a[i-1][0]), w+1)):
        memo[i][j] = max(memo[i][j], memo[i - 1][j - int(a[i - 1][0])] + int(a[i - 1][1]))
        ans = max(ans, memo[i][j])
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
def knapsack1(pos, curr_weight):
    if pos == len(W):
        return 0
    if curr_weight - W[pos] >= 0:
        return max(knapsack1(pos + 1, curr_weight - W[pos]) + V[pos], knapsack1(pos + 1, curr_weight))
    else:
        return knapsack1(pos + 1, curr_weight)


if __name__ == '__main__':
    # N W
    NW = input().rstrip().split()
    n = int(NW[0])
    w = int(NW[1])

    W = []
    V = []

    for _ in range(n):
        inp = input().rstrip().split()
        W.append(int(inp[0]))
        V.append(int(inp[1]))

    print(knapsack1(0, w))

Submission status: Time Limit Exceeded

Solution code:
inp = list(map(int,input().split()))
n=inp[0]
tot=inp[1]
weight=[]
val=[]
for i in range(n):
    inp = list(map(int,input().split()))
    weight.append(inp[0])
    val.append(inp[1])
ans=[-1]*(tot+1)
ans[0]=0
for i in range(len(weight)):
    for j in range(len(ans)-1,weight[i]-1,-1):
        ans[j]=max(ans[j],ans[j-weight[i]]+val[i])
print (max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


n, w = LI()
wv = LIR(n)
weight = [wv[i][0] for i in range(n)]
value = [wv[i][1] for i in range(n)]
# dp[i][j] : 重さ制限 j 、品物 i までを選べる状態での価値の最大値
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(w + 1):
        if j - weight[i] >= 0:  # 品物 i が選べるかどうか
            dp[i + 1][j] = max(
                dp[i][j],  # 選ばない
                dp[i][j - weight[i]] + value[i]  # 選ぶ
            )
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def chmax(a, b):
    if a > b:
        return a
    else:
        return b


def main():
    N, W = map(int, input().split())
    wv = [None] * N
    for i in range(N):
        wv[i] = tuple(map(int, input().split()))

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i, (w, v) in enumerate(wv, start=1):
        dp_i = dp[i]
        dp_im = dp[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp_i[j] = dp_im[j]
            else:
                dp_i[j] = chmax(dp_im[j - w] + v, dp_im[j])

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    wv = [None] * N
    for i in range(N):
        wv[i] = tuple(map(int, input().split()))

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i, (w, v) in enumerate(wv, start=1):
        dp_i = dp[i]
        dp_im = dp[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp_i[j] = dp_im[j]
            elif dp_im[j - w] + v > dp_im[j]:
                dp_i[j] = dp_im[j - w] + v
            else:
                dp_i[j] = dp_im[j]

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def readinput():
    n,w=list(map(int,input().split()))
    wlist=[]
    vlist=[]
    for _ in range(n):
        ww,vv=list(map(int,input().split()))
        wlist.append(ww)
        vlist.append(vv)
    return n,w,wlist,vlist

def main(n,W,w,v):
    dp=[]
    for _ in range(n+1):
        dp.append([0]*(W+1))
    for i in range(1,n+1):
        for j in range(W+1):
            if j-w[i-1]>=0:
                dp[i][j]=max(dp[i-1][j-w[i-1]]+v[i-1], dp[i][j])
            dp[i][j]=max(dp[i-1][j], dp[i][j])
    return dp[n][W]

if __name__=='__main__':
    n,w,wlist,vlist=readinput()
    ans=main(n,w,wlist,vlist)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, WM = map(int, input().split())
W = []
V = []
dp = [[0] * (WM + 1) for _ in range(N + 1)]

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

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

print(dp[N][WM])

Submission status: Time Limit Exceeded

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

dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1, N+1):
    row = dp[i]; row_before = dp[i-1]
    v_i = v[i]; w_i = w[i]
    for sum_w in range(1, W+1):
        if sum_w - w_i >= 0:
            row[sum_w] = max(row_before[sum_w - w_i] + v_i, row_before[sum_w])
        else:
            row[sum_w] = row_before[sum_w]
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wv = [[0 for i in range(2)] for j in range(N)]
dp = [[0 for i in range(N+1)] for j in range(W+1)]

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

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

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

Submission status: Time Limit Exceeded

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

DP=[[0]*(W+1) for _ in range(N+1)]
for j in range(1,N+1):
    if L[j-1][0]<=W:
        for k in range(L[j-1][0],W+1):
            DP[j][k]=max(DP[j-1][k],DP[j-1][k-L[j-1][0]]+L[j-1][1])
        for l in range(L[j-1][0]):
            DP[j][l]=DP[j-1][l]
    else:
        for m in range(0,W+1):
            DP[j][m]=DP[j-1][m]
            
print(DP[N][W])

Submission status: Time Limit Exceeded

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

main()

Submission status: Time Limit Exceeded

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

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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 = np.zeros((N+1, W+1), dtype=np.int)
for i in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1,sum_w] = max(dp[i+1,sum_w], dp[i][sum_w-w[i]] + v[i])
        dp[i+1,sum_w] = max(dp[i+1,sum_w], dp[i][sum_w])
print(dp[N][W])

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())
weight = []
value = []
for _ in range(N):
    x, y = map(int, input().split())
    weight.append(x)
    value.append(y)

dp = np.zeros((N + 1, W + 1))
for i in range(N):
    for j in range(W + 1):
        if weight[i] <= j:
            dp[i + 1, j] = max(dp[i, j - weight[i]] + value[i], dp[i, j])
        else:
            dp[i + 1, j] = dp[i, j]

print(int(dp[N, W]))

Submission status: Time Limit Exceeded

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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

def main():
    n, w = map(int,input().split())
    wei = []
    val = []
    for i in range(n):
        a, b = map(int,input().split())
        wei.append(a)
        val.append(b)

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

    for i in range(n):
        for sum_w in range(w+1):
            
            if sum_w - wei[i] >= 0:
                dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - wei[i]] + val[i])

            
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

    print(dp[n][w])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
def knapsack(weights,values,capacity,n,memo):
    if(memo[n][capacity]!=-1):
        return memo[n][capacity]
    if(n==0 or capacity==0):
        return 0
    val=0
    if(weights[n-1]<=capacity):
        memo[n][capacity]=max(values[n-1]+knapsack(weights,values,capacity-weights[n-1],n-1,memo),knapsack(weights,values,capacity,n-1,memo))
        return memo[n][capacity]
    memo[n][capacity]=knapsack(weights,values,capacity,n-1,memo)
    return memo[n][capacity]

n,capacity=map(int,stdin.readline().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,stdin.readline().split())
memo=[[-1]*(capacity+1) for i in range(n+1)]
stdout.write(str(knapsack(weights,values,capacity,n,memo)))

Submission status: Time Limit Exceeded

Solution code:
def knapsack(weights,values,capacity,n,memo):
    if(memo[n][capacity]!=-1):
        return memo[n][capacity]
    if(n==0 or capacity==0):
        return 0
    val=0
    if(weights[n-1]<=capacity):
        memo[n][capacity]=max(values[n-1]+knapsack(weights,values,capacity-weights[n-1],n-1,memo),knapsack(weights,values,capacity,n-1,memo))
        return memo[n][capacity]
    memo[n][capacity]=knapsack(weights,values,capacity,n-1,memo)
    return memo[n][capacity]

n,capacity=map(int,input().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,input().split())
memo=[[-1]*(capacity+1) for i in range(n+1)]
print(knapsack(weights,values,capacity,n,memo))

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] * (W+1) for _ in range(N+1)]

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

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
items = []
for _ in range(n):
  items.append(list(map(int, input().split())))
tables = [[0]*(w+1) for _ in range(n+1)]

for i in range(1,n+1):
  now_item = items[i-1]
  weight = now_item[0]
  value = now_item[1]
  tables[i] = tables[i-1].copy()
  for j in range(weight,w+1):
    tables[i][j] = max(tables[i][j], tables[i-1][j-weight]+value)
      
print(tables[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
items = []
for _ in range(n):
  items.append(list(map(int, input().split())))
tables = [[0]*(w+1) for _ in range(n+1)]

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

Submission status: Time Limit Exceeded

Solution code:
import copy

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

max_v_per_w = [0] * (W+1)
for i in range(N):
    w, v = wv[i]
    tmp = copy.deepcopy(max_v_per_w)
    for j in range(w, W+1):
        max_v_per_w[j] = max(tmp[j], tmp[j-w]+v)
        
print(max(max_v_per_w))

Submission status: Time Limit Exceeded

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

dp=[[0 for w in range(W+1)] for n in range(N+1)]
for n in range(1,N+1):
    for i in range(W+1):
        #各nにつき重みiを超えない最大値を求める
        tmp=l[n-1][0]
        if  tmp+i<=W:
            dp[n][tmp+i]=max(dp[n][tmp+i],dp[n-1][i]+l[n-1][1])
        dp[n][i]=max(dp[n][i],dp[n-1][i])

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

print(res)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
#D
N,W=map(int,input().split())
w_list=[]
v_list=[]

for i in range(N):
    w1,v1=map(int,input().split())
    w_list.append(w1)
    v_list.append(v1)
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):
    for w in range(W+1):
        if w_list[i]<=w:
            dp[i+1][w]=max(dp[i][w-w_list[i]]+v_list[i],dp[i][w])
        else:
            dp[i+1][w]=dp[i][w]
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(N)]
x.insert(0, [0, 0])
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for sum_m in range(1, W+1):
        #品物(w[i], v[i])を選ぶとき
        if sum_m >= x[i][0]:
            dp[i][sum_m] = max(dp[i][sum_m], dp[i-1][sum_m-x[i][0]] + x[i][1])
        #品物(w[i], v[i])を選ばないとき
        dp[i][sum_m] = max(dp[i][sum_m], dp[i-1][sum_m])
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:

N, W = [int(x) for x in input().split()]
wt = []
val = []
K = [[0 for x in range(W+1)]for x in range(N+1)]
for i in range(N):
    k, q = [int(x) for x in input().split()]
    wt.append(k)
    val.append(q)

for i in range(N + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1]
+ K[i-1][w-wt[i-1]],  K[i-1][w])
            else:
                K[i][w] = K[i-1][w]

print(K[N][W])