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 math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

N, W = imn()
wv = [iln() for _ in range(N)]

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

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

Submission status: Time Limit Exceeded

Solution code:
n, ww = 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] * (100100) for i in range(110)]

for i in range(n):
    for j in range(ww + 1):
        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 + 1][j], dp[i][j])

print(dp[n][ww])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,W = map(int,input().split())
w = []
h = []
for i in range(n):
    a,b = map(int,input().split())
    w.append(a)
    h.append(b)
dp = [[0]*(W+1) for i in range(n+1)]
for i in range(n):#i番目の種類の荷物まで使う
    for j in range(W+1):
        if j < w[i]: dp[i+1][j] = dp[i][j]#更新できない
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+h[i])
print(dp[n][W])

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(2147483647)

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

def dfs(i,w):
    if (i,w) in dic: return dic[(i,w)]
    if i == N or w <=0: 
        dic[(i,w)] = 0
        return 0
    ma = 0 
    res1 = res2 = 0 
    if A[i][0] <=w:
        res1 = dfs(i + 1,w - A[i][0]) + A[i][1]
    res2 = dfs(i + 1,w)
    ma = max(res1,res2)
    dic[(i,w)] = ma
    return ma
dic = {}
res = dfs(0,W)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(2147483647)

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

def dfs(i,w):
    if (i,w) in dic: return dic[(i,w)]
    if i == N or w <=0: return 0
    ma = 0 
    res1 = res2 = 0 
    if A[i][0] <=w:
        res1 = dfs(i + 1,w - A[i][0]) + A[i][1]
    res2 = dfs(i + 1,w)
    ma = max(res1,res2)
    dic[(i,w)] = ma
    return ma
dic = {}
res = dfs(0,W)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(2147483647)

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

def dfs(w,s):
    if (w,s) in dic: return dic[(w,s)]
    ma = 0 
    ls = set(s)
    for idx in range(N):
        if idx not in ls and A[idx][0] <= w:
            ls.add(idx)
            res = dfs(w - A[idx][0],tuple(ls)) + A[idx][1]
            ma = max(res,ma)
            ls.remove(idx)
    dic[(w,s)] = ma
    return ma
dic = {}
seen = set()
res = dfs(W,tuple(seen))
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(N)]
DP = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
  for j in range(1,W+1):
    DP[i][j] = max(DP[i][j],DP[i-1][j])
    if j-wv[i-1][0] >= 0:
      DP[i][j] = max(DP[i][j],DP[i-1][j-wv[i-1][0]]+wv[i-1][1])
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 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):
    DP[i][j] = max(DP[i][j],DP[i-1][j])
    if j-wv[i-1][0] >= 0:
      DP[i][j] = max(DP[i][j],DP[i-1][j-wv[i-1][0]]+wv[i-1][1])
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)]

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

for i in range(N):
    weight = wv[i][0]
    value = wv[i][1]
    for w in range(W+1):
        # 重量に収まる場合のみ価値を加える
        if weight <= w:
            dp[i+1][w] = max(dp[i][w-weight] + value, dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(max(dp[-1]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

    for i in range(N):
        for sum_w in range(W+1):

            if sum_w - wv[i][0] >= 0:
                DP[i+1][sum_w] = max(
                    DP[i][sum_w - wv[i][0]] + wv[i][1],
                    DP[i+1][sum_w])

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

    print(DP[N][W])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(N, W):
    dp = [0] * (W + 1)
    for item in range(1, N + 1):
        w, v = list(map(int, input().split()))
        for i in range(W, w - 1, -1):  #
            if v + dp[i - w] > dp[i]:
                dp[i] = v + dp[i - w]

    print(max(dp))


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

Submission status: Time Limit Exceeded

Solution code:
def solve(N, W, weightValues):
    dp = [0] * (W + 1)
    for item in range(1, N + 1):
        w, v = weightValues[item - 1]
        for i in range(W, w - 1, -1):  #
            dp[i] = max(dp[i], v + dp[i - w])

    print(max(dp))


N, W = map(int, input().split())
weightValues = sorted([list(map(int, input().split())) for i in range(N)])
solve(N, W, weightValues)

Submission status: Time Limit Exceeded

Solution code:
def solve(N, W, weight_values):
    dp = [0 for _ in range(W + 1)]
    for i in range(N):
        wi, vi = weight_values[i]
        for w in range(W, wi - 1, -1):
            dp[w] = max(dp[w], vi + dp[w - wi])
    print(dp[W])

def iln():
    return list(map(int, input().split()))


N, W = iln()
w_v = []
for i in range(N):
    w_v.append(iln())

solve(N, W, w_v)

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] * (W + 1)]
for i in range(1, N + 1):
    row = DP[i - 1][:]
    for j in range(W, -1, -1):
        new_j = j + w[i - 1]
        if 0 <= new_j <= W:
            row[new_j] = max(row[new_j], row[j] + v[i - 1])
    DP.append(row)
print(DP[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, w = map(int ,input().split())
items = []
for i in range(n):
    array = list(map(int, input().split()))
    items.append(array)
dp = np.zeros((n+1, w+1))


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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import namedtuple

Item = namedtuple('Item', 'w v')

N, W = (int(x) for x in input().split())

items = []

for _ in range(N):
  w, v = (int(x) for x in input().split())
  items.append(Item(w, v))

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

for i in range(N):
  for w in range(W + 1):
    if i == 0:
      # 1行目を初期化
      memo[i][w] = items[i].v if items[i].w <= w else 0
      continue
    if w < items[i].w:
      # 入らなければひとつ上の行の値をそのまま使う
      memo[i][w] = memo[i - 1][w]
      continue
    memo[i][w] = max(memo[i - 1][w], memo[i - 1][w - items[i].w] + items[i].v)

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

Submission status: Time Limit Exceeded

Solution code:
def chmax(a, b):
    if a < b:
        a = b
        return a
    else:
        return a


n, w = map(int, input().split())
ls = [[int(_) for _ in input().split()] for _ in range(n)]

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

for i in range(1, n + 1):
    for sumw in range(w + 1):
        if sumw + ls[i - 1][0] <= w:
            dp[i][sumw + ls[i - 1][0]] = chmax(dp[i][sumw + ls[i - 1][0]], dp[i - 1][sumw] + ls[i - 1][1])
        
        dp[i][sumw] = chmax(dp[i][sumw], dp[i - 1][sumw])

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wvlist = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(N):
    for sum_w in range(W + 1):
        if sum_w >= wvlist[i][0]:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - wvlist[i][0]] + wvlist[i][1])
        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:
N, W = map(int, input().split())
items = []
for _ in range(N):
    w, v = map(int, input().split())
    items.append({'w': w, 'v': v})

items.sort(key=lambda d: d['v'] / d['w'])

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

for i in range(1, N + 1):
    w = items[i - 1]['w']
    v = items[i - 1]['v']
    for j in range(1, W + 1):
        if w > j:
            dp[i][j] = dp[i][j - 1]
        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:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        dp[j]=max(dp[j],dp[j-w]+v) 
    
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

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

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

Submission status: Time Limit Exceeded

Solution code:
n, total_weight = [int(x) for x in input().split()]
items = (map(int, input().split()) for _ in range(n))

dp_table = [0] * (total_weight + 1)

for w,v in items:
    for j in range(total_weight, w-1, -1):
        now_opt = dp_table[j - w] + v
        if dp_table[j] < now_opt:
            dp_table[j] = now_opt

print(dp_table[total_weight])

Submission status: Time Limit Exceeded

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

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

def solve(items, w=W, cur_item=0):
    if cur_item >= len(items):
        return 0
    
    cur_w, cur_v = items[cur_item]

    dont_take = solve(items, w, cur_item+1)

    if cur_w <= w:
        take = solve(items, w-cur_w, cur_item+1) + cur_v
    else:
        take = 0
    
    return max(take, dont_take)
        
print(solve(items, W))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split(" "))
weights = []
values = []

for _ in range(N):
    w, v = map(int, input().split(" "))
    weights.append(w)
    values.append(v)

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

N, W = list(map(int, input().split()))
item_list = []

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

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

for i in range(1, N + 1):
    w, v = item_list[i - 1]
    for j in range(W + 1):
        # 品物iを入れない場合
        before_best_value = dp_table[i - 1][j]
        dp_table[i][j] = before_best_value
        # 品物iを入れる場合
        if j - w < 0:
            continue
        value = dp_table[i - 1][j - w] + v
        best_value = max(before_best_value, value)
        dp_table[i][j] = best_value

ans = max(dp_table[-1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:

n,kapacitet=map(int,input().split())
tezine=[0]
vrijednosti=[0]

for i in range(n):
      tezina,vrijednost=map(int,input().split())
      tezine.append(tezina)
      vrijednosti.append(vrijednost)

mat=[[0 for i in range(n)] for j in range(kapacitet)]
def ks(n,kapacitet):
      #bazna težina
      if n==0 or kapacitet==0:
            result=0
      #ako je trenutni element veći od kapaciteta idemo u novu rekurziju s n-1
      #tj prelazimo na sljedeći element
      elif tezine[n]>kapacitet:
            result=ks(n-1,kapacitet)
      else:
            #tmp1 ako ne stavljamo element u kapacitet
            tmp1=ks(n-1,kapacitet)
            #ako stavljamo element u kapacitet
            tmp2=vrijednosti[n]+ks(n-1,kapacitet-tezine[n])
            result=max(tmp1,tmp2)
      return result

print(ks(n,kapacitet))

Submission status: Time Limit Exceeded

Solution code:
n,kapacitet=map(int,input().split())
tezine=[]
vrijednosti=[]

for i in range(n):
      tezina,vrijednost=map(int,input().split())
      tezine.append(tezina)
      vrijednosti.append(vrijednost)
def knapSack(kapacitet, tezine, vrijednosti, n): 
    mat = [[0 for x in range(kapacitet + 1)] for x in range(n + 1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n + 1): 
        for j in range(kapacitet + 1): 
            if i == 0 or j == 0: 
                mat[i][j] = 0
            elif tezine[i-1] <= j: 
                mat[i][j] = max(vrijednosti[i-1] + mat[i-1][j-tezine[i-1]],  mat[i-1][j]) 
            else: 
               mat[i][j] = mat[i-1][j] 
  
    return mat[n][kapacitet]
print(knapSack(kapacitet, tezine, vrijednosti, n))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数

N,W = imn()
wv = [iln() for _ in range(N)]

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

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

        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:
def solve(N, W, weight_values):
  dp = [0 for _ in range(W + 1)]
  dp[0] = 0

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

  print(dp[W])

  
def iln(): return list(map(int, input().split()))


N, W = iln()
w_v = []
for i in range(N):
  w_v.append(iln())
  
solve(N, W, w_v)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def solver():
	N,W = map(int, input().split())
	item = []
	for i in range(N):
		item.append(list(map(int, input().split())))
	dp = [0 for _ in range(W+1)]

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

solver()

Submission status: Time Limit Exceeded

Solution code:
def solver():
	N,W = map(int, input().split())
	item = []
	for i in range(N):
		item.append(list(map(int, input().split())))
	dp = [0 for _ in range(W+1)]

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

solver()

Submission status: Time Limit Exceeded

Solution code:
def solver():
	N,W = map(int, input().split())
	item = []
	for i in range(N):
		item.append(list(map(int, input().split())))
	dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

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

solver()

Submission status: Time Limit Exceeded

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

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

for n in range(1,N+1):
    for w in range(W+1):
        if w>=w_li[n-1][0]:
            li[w][n] = max(li[w][n-1] , li[w-w_li[n-1][0]][n-1]+w_li[n-1][1])
        else:
            li[w][n] = li[w][n-1]
print(li[W][N])

Submission status: Time Limit Exceeded

Solution code:
# D - Knapsack 1
from collections import defaultdict


def main():
    N, W, *WV = map(int, open(0).read().split())
    dp = defaultdict(int)
    dp[0] = 0
    for w, v in zip(*[iter(WV)] * 2):
        for cur_w, cur_v in tuple(dp.items()):
            if w + cur_w <= W:
                dp[w + cur_w] = max(dp[w + cur_w], v + cur_v)
    print(max(dp.values()))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

items = []

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

    items.append((w, v))

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

for i in range(1, N + 1):
    w, v = items[i - 1]
    for p in range(W):
        dp[i][p] = max(dp[i][p], dp[i - 1][p])

        if p + w <= W:
            dp[i][p + w] = max(dp[i][p + w], dp[i - 1][p] + v)

print(max(dp[N]))

Submission status: Time Limit Exceeded

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

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

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

print(max(dp[N]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import random

import sys
sys.setrecursionlimit(100000000)

# N, W = 100, 20000
# W_V = [[random.randint(1,10000), random.randint(1,1000000)] for i in range(N)]
N, W = map(int, raw_input().split())
W_V = [list(map(int, raw_input().split())) for i in range(N)]
memo = [[None for j in range(W+1)] for i in range(N+1)]

def get_weight_and_value_of_nth_item(n):
    if n >= N:
        return 0, 0
    else:
        return W_V[n]

def get_max_val_starting_from_element(i, weight):
    if i >= N or weight <= 0:
        return 0

    if memo[i][weight] is not None:
        return memo[i][weight]
    w, v = get_weight_and_value_of_nth_item(i)
    ans = max(
        (v + get_max_val_starting_from_element(i+1, weight - w)) if weight - w >= 0 else 0,
        get_max_val_starting_from_element(i+1, weight))

    memo[i][weight] = ans
    return ans

print get_max_val_starting_from_element(0, W)

Submission status: Time Limit Exceeded

Solution code:
import random

import sys
sys.setrecursionlimit(100000000)

# N, W = 80, 5000
# W_V = [[random.randint(1,10000) for i in range(2)] for i in range(N)]
N, W = map(int, raw_input().split())
W_V = [list(map(int, raw_input().split())) for i in range(N)]
memo = {}

def get_weight_and_value_of_nth_item(n):
    if n >= N:
        return 0, 0
    else:
        return W_V[n]

def get_max_val_starting_from_element(i, weight):
    if i >= N or weight <= 0:
        return 0

    if (i, weight) in memo:
        return memo[i, weight]
    w, v = get_weight_and_value_of_nth_item(i)
    ans = max(
        (v + get_max_val_starting_from_element(i+1, weight - w)) if weight - w >= 0 else 0,
        get_max_val_starting_from_element(i+1, weight))

    memo[i, weight] = ans
    return ans

for i in range(N-1, -1, -1):
    get_max_val_starting_from_element(i, W)

print memo[0, W]

Submission status: Time Limit Exceeded

Solution code:
import random

import sys
sys.setrecursionlimit(100000000)

# N, W = 80, 5000
# W_V = [[random.randint(1,10000) for i in range(2)] for i in range(N)]
N, W = map(int, raw_input().split())
W_V = [list(map(int, raw_input().split())) for i in range(N)]
memo = {}

def get_weight_and_value_of_nth_item(n):
    if n >= N:
        return 0, 0
    else:
        return W_V[n]

def get_max_val_starting_from_element(i, weight):
    if i >= N or weight <= 0:
        return 0

    if (i, weight) in memo:
        return memo[i, weight]
    w, v = get_weight_and_value_of_nth_item(i)
    ans = max(
        (v + get_max_val_starting_from_element(i+1, weight - w)) if weight - w >= 0 else 0,
        get_max_val_starting_from_element(i+1, weight))

    memo[i, weight] = ans
    return ans


print get_max_val_starting_from_element(0, W)

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int,input().split())
items = []
for i in range(n):
    items.append(list(map(int,input().split())))
possibilities = []
for wi, vi in items:
    to_add =[]
    for wp, vp in possibilities:
        if wp + wi <= w:
            to_add.append([wp+wi, vp + vi])
    possibilities += to_add + [[wi, vi]]
print(max([x for y,x in possibilities]))

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,W=LI()
  dp=[[0 for _ in range(W+1)]for __ in range(n+1)]
  w=[]
  v=[]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

  # dp[i+1][j] iまでで最大化
  for i in range(n):
    for j in range(W+1):
      if j<w[i]:
        dp[i+1][j]=dp[i][j]
      else:
        dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])

  return dp[n][W]

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split(' '))
pair = [tuple(map(int, input().split(' '))) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        if sum_w >= pair[i][0]:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-pair[i][0]] + pair[i][1])
        else:
            dp[i+1][sum_w] = dp[i][sum_w]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, W = map(int, input().split(' '))
pair = [tuple(map(int, input().split(' '))) for _ in range(N)]
dp = np.zeros((N+1, W+1), dtype=int)
for i in range(N):
    for sum_w in range(W+1):
        if sum_w >= pair[i][0]:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-pair[i][0]] + pair[i][1])
        else:
            dp[i+1][sum_w] = dp[i][sum_w]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

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

for w, v in L:
  con += w
  for i in range(min(con, W), w - 1, -1):
    if dp[i] < dp[i - w] + v:
      dp[i] = dp[i - w] + v

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
#重さ、価値の順
dp=[[0]*(w+1) for i in range(n+1)]
#配列のインデックスを重さに対応させる

for i in range(n):
    for sum_w in range(w+1):
        
        if sum_w-l[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-l[i][0]]+l[i][1])
        #l[i]を入れるとき
        dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w])
        #入れない時
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, w = map(int, input().split())
dp = np.zeros((n+1, w+1))

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

Submission status: Time Limit Exceeded

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

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