Problem:


Score : 100 points

Problem Statement

There are N items, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.

Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^9

1 \leq w_i \leq W

1 \leq v_i \leq 10^3

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.

Sample Input 2

1 1000000000
1000000000 10

Sample Output 2

10

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Time Limit Exceeded

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()

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

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

dp = [[float("INF")]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
  for v_sum in range(V+1):
    if v_sum >= v[i-1]:
      dp[i][v_sum] = min(dp[i-1][v_sum - v[i-1]] + w[i-1], dp[i-1][v_sum])
    else:
      dp[i][v_sum] = dp[i-1][v_sum]

ans = 0
for v_sum in range(V+1):
  if dp[N][v_sum] <= W:
    ans = v_sum
print(ans)

Submission status: Time Limit Exceeded

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



V_max = 0
# 価値の最大値を求める
Weights=[]
Values=[]
for i in range(N):
    w_i,v_i = map(int,input().split())
    Weights.append(w_i)
    Values.append(v_i)
    V_max=max(V_max,v_i)

# print(*Data,sep="\n")
# print(V_max)

NV = N*V_max
#DPテーブル
dp=[]
for k in range(N+1):
    dp.append([float('inf')]*( NV + 1 ))
dp[0][0]=0

# print(*dp,sep="\n")

for i in range(N):
    for v in range(NV+1):
        if v - Values[i] >= 0:
            dp[i+1][v] = min( dp[i][v] , dp[i][v-Values[i]] + Weights[i] )
        else:
            dp[i+1][v] = dp[i][v]

# print(*dp,sep="\n")
dp[N].reverse()

# print(dp[N])
print([NV-dp[N].index(l) for l in dp[N] if l<=W][0])

Submission status: Time Limit Exceeded

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



V_max = 0
# 価値の最大値を求める
Weights=[]
Values=[]
for i in range(N):
    w_i,v_i = map(int,input().split())
    Weights.append(w_i)
    Values.append(v_i)
    V_max=max(V_max,v_i)

# print(*Data,sep="\n")
# print(V_max)

NV = N*V_max
#DPテーブル
dp=[]
for k in range(N+1):
    # if k==0:
    #     dp.append( [0]*( NV+1 ) )
    # else:
    dp.append([float('inf')]*( NV + 1 ))
dp[0][0]=0

# print(*dp,sep="\n")

for i in range(N):
    for v in range(NV+1):
        if v - Values[i] >= 0:
            dp[i+1][v] = min( dp[i][v] , dp[i][v-Values[i]] + Weights[i] )
        else:
            dp[i+1][v] = dp[i][v]

# print(*dp,sep="\n")
dp[N].reverse()

# print(dp[N])
print([NV-dp[N].index(l) for l in dp[N] if l<=W][0])

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":

    """
    d[i]: Min possible weight that can add values equal to exxactly i
    i = 0 to sum_values
    """

    N, W = map(int, input().split())
    values, weights = [], []

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

    dp = [float('inf')] * (sum(values) + 1)
    dp[0] = 0

    for i in range(N):
        weight, value = weights[i], values[i]
        for value_already in range(sum(values) - value, -1, -1):
            dp[value + value_already] = min(dp[value + value_already],
                                            dp[value_already] + weight)

    ans = 0    
    for i in range(sum(values) + 1):
        if dp[i] <= W:
            ans = max(ans, i)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import sys
inf = 10**9+7
mod = 10**9+7

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = map(int, input().split())
inf = 10**18
M = 10**5
#dp = [0 for i in range(10**5+1)]


dp = [[inf for i in range(M+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, val = map(int, input().split())
    for v in range(M+1):
        if v >= val:
            dp[i+1][v] = min(dp[i][v-val] + w, dp[i][v])
        else:
            dp[i+1][v] = dp[i][v]

for i in range(M+1):
    if dp[N][M-i] <= W:
        print(M-i)
        break

Submission status: Time Limit Exceeded

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

dp = [[float("inf") for i in range(1000*N+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for v in range(1000*N+1):
        if wv[i][1] <= v:
            dp[i+1][v] = min(dp[i][v], dp[i][v-wv[i][1]] + wv[i][0])
        else:
            dp[i+1][v] = dp[i][v]
ans = 0
for i in range(1000*N+1):
    if dp[N][i]<=W:
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(c, a):
    dp = {c: 0}
    for w, p in a:
        dp2 = dp.copy()
        for rc, v in dp.items():
            if rc >= w:
                dp2[rc-w] = max(dp2.get(rc-w, 0), v + p)
        dp = dp2
    return max(dp.values())
  
n, k = map(int, input().split())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
print(solve(k, a))

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
weights, values = zip(*[tuple(map(int, input().split())) for _ in range(n)])
UV = 10**5
INF = 10**10
dp = [INF]*(UV+1)
dp[0] = 0

for i in range(1, n+1):
    for j in reversed(range(1, UV+1)):
        if j-values[i-1] < 0:
            continue
        dp[j] = min(dp[j], dp[j-values[i-1]]+weights[i-1])

ans = 0
for j in reversed(range(UV+1)):
    if dp[j] <= w:
        ans = j
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
dpv = [10 ** 20 for i in range(10**5+1)]
dpv[0] = 0
for i in range(n):
  weight,value = map(int,input().split())
  for j in range(10**5-value,-1,-1):
    dpv[j+value] = min(dpv[j+value],dpv[j]+weight)
for i in range(10**5,-1,-1):
  if dpv[i] <= w:
    print(i)
    exit()

Submission status: Time Limit Exceeded

Solution code:
"""
E-Knapsack2
Wが10**9まであるのでdpの置き方を工夫する。
dp[i]:=価値がiのときのナップザックの重さ
"""
N,W = map(int,input().split())
dp = [0]+[W+1]*(N*10**3)
for i in range(N):
    w,v = map(int,input().split())
    for j in range(N*10**3+1-v)[::-1]:
        dp[j+v] = min(dp[j+v],dp[j]+w)
for i in range(N*10**3+1)[::-1]:
    if dp[i]<=W:
        print(i)
        exit()

Submission status: Time Limit Exceeded

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

INF = 10**16

def solve(N: int, W: int, w: "List[int]", v: "List[int]"):

    V = max(v) * N
    dp = []
    for _ in range(N):
        l = [INF]*(V + 1)
        dp.append(l)
    
    # initialize
    for j in range(V + 1):
        dp[0][j] = w[0] if j == v[0] else INF
        dp[0][0] = 0

    for i in range(1, N):
        for j in range(V + 1):
            if j >= v[i]:
                dp[i][j] = min(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]
    
    res = 0
    for j in range(V + 1):
        if dp[N - 1][j] <= W:
            res = j
    print(res)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    # 見つからなかったとき
    return None


n, w = map(int, readline().split())
wv = [list(map(int, readline().split())) for i in range(n)]
dp = [0]
check = [0]
size = 1
for ww, vv in wv:
    for i in range(size):
        g = ww + check[i]
        v = vv + dp[i]
        if g > w:
            continue
        else:
            search = binary_search(check, g)
            if search:
                if dp[search] < v:
                    dp[search] = v
            else:
                dp.append(v)
                check.append(g)
                size += 1

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, w = map(int, readline().split())
wv = [list(map(int, readline().split())) for i in range(n)]
dp = [0]
check = [0]
size = 1
for ww, vv in wv:
    for i in range(size):
        g = ww + check[i]
        v = vv + dp[i]
        if g > w:
            continue
        else:
            if g in check:
                index = check.index(g)
                if dp[index] < v:
                    dp[index] = v
            else:
                dp.append(v)
                check.append(g)
                size += 1

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, w = map(int, readline().split())
wv = [list(map(int, readline().split())) for i in range(n)]
inf = float('inf')
dp = [0]
check = [0]
for ww, vv in wv:
    for i in range(len(dp)):
        g = ww + check[i]
        v = vv + dp[i]
        if g > w:
            continue
        else:
            if g in check:
                index = check.index(g)
                if dp[index] < v:
                    dp[index] = v
            else:
                dp.append(v)
                check.append(g)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,W=map(int,input().split())
wv=[[int(j) for j in input().split()] for i in range(n)]
dp=[[0]*110000 for i in range(110)]
INF=10**10
for j in range(1,110000):
  dp[0][j]=INF

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

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
v = []
wt = []
for _ in range(n):
    x,y=map(int,input().split())
    wt.append(x)
    v.append(y)
a = [[0 for x in range(w+1)] for x in range(n+1)] 
for i in range(n+1):
    for j in range(w+1):
        if i == 0 or j==0:
            a[i][j]=0
        elif wt[i-1]<=j:
            a[i][j]=max(a[i-1][j],(v[i-1]+a[i-1][j-wt[i-1]]))
        else:
            a[i][j]=a[i-1][j]
print(a[n][w])

Submission status: Time Limit Exceeded

Solution code:
N,W = list(map(int,input().split()))
w_l = []
v_l = []
for i in range(N):
    w,v = list(map(int,input().split()))
    w_l.append(w)
    v_l.append(v)
def knapsack(N,W,w_l,v_l):
    if (N==0 or W==0):
        return 0
    elif(w_l[N-1]>W):
        return knapsack(N-1,W,w_l,v_l)
    
    else:
        return max(knapsack(N-1,W,w_l,v_l), v_l[N-1]+knapsack(N-1,W-w_l[N-1],w_l,v_l))
ans = knapsack(N,W,w_l,v_l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,W = map(int,input().split())
dp = [0]*(10**3+1)+[10**12]*(10**5)
for i in range(N):
    w,v = map(int,input().split())
    for j in range(len(dp)-1,1000,-1):
        dp[j] = min(dp[j],dp[j-v]+w)
print(bisect.bisect_right(dp,W)-1001)

Submission status: Time Limit Exceeded

Solution code:
# Python3 implementation of the approach 
V_SUM_MAX = 100*10**3+5
N_MAX = 100+5
W_MAX = 10**9+5
  
# To store the states of DP 
dp = [[ 0 for i in range(N_MAX)] 
          for i in range(V_SUM_MAX + 1)] 
v = [[ 0 for i in range(N_MAX)] 
         for i in range(V_SUM_MAX + 1)] 
  
# Function to solve the recurrence relation 
def solveDp(r, i, w, val, n): 
      
    # Base cases 
    if (r <= 0): 
        return 0
    if (i == n): 
        return W_MAX 
    if (v[r][i]): 
        return dp[r][i] 
  
    # Marking state as solved 
    v[r][i] = 1
  
    # Recurrence relation 
    dp[r][i] = min(solveDp(r, i + 1, w, val, n),  
            w[i] + solveDp(r - val[i], i + 1, 
                            w, val, n)) 
    return dp[r][i] 
  
# Function to return the maximum weight 
def maxWeight( w, val, n, c): 
  
    # Iterating through all possible values 
    # to find the the largest value that can 
    # be represented by the given weights 
    for i in range(V_SUM_MAX, -1, -1): 
        if (solveDp(i, 0, w, val, n) <= c): 
            return i 
  
    return 0
  
n,C = map(int, input().split())
w = [] 
val = [] 
for i in range(n):
    wei,vv = map(int, input().split())
    w.append(wei)
    val.append(vv)    

print(maxWeight(w, val, n, C))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout

print = stdout.write
input = stdin.readline
INF = 1e10
n,W = map(int,input().split())

wgt = [0]
val = [0]
for i in range(n):
    w,v = map(int,input().split())
    wgt.append(w)
    val.append(v)

max_val=sum(val)    
dp=[[INF for x in range(max_val+1)] for x in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(1,n+1):
    vi = val[i];wi = wgt[i]
    for V in range(1,max_val+1):
        if vi<= V:
            dp[i][V] = min(wi+dp[i-1][V-vi],dp[i-1][V])
        else:
            dp[i][V]=dp[i-1][V]
res = 0
for i in range(max_val,-1,-1):
    if dp[n][i] <= W:
        res = i
        break
print(str(res))

Submission status: Time Limit Exceeded

Solution code:
#input
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())

#output
import numpy as np
V = max(v)
INF = 10**10
dp = np.full((N+1, N*V+1), INF)
dp[0, 0] = 0

for i in range(N):
    for j in range(N*V+1):
        if j < v[i]:
            dp[i+1, j] = dp[i, j]
        else:
            dp[i+1, j] = min(dp[i, j], dp[i, j-v[i]]+w[i])
        
answer = 0
for i in range(N*V+1):
    if dp[N, i] <= W:
        answer = i

print(answer)

Submission status: Time Limit Exceeded

Solution code:
#input
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())

#output
import numpy as np
V = max(v)
INF = 10**6
dp = np.zeros((N+1, N*V+1), int)
dp[0] = INF
dp[0, 0] = 0

for i in range(N):
    for j in range(N*V+1):
        if j < v[i]:
            dp[i+1, j] = dp[i, j]
        else:
            dp[i+1, j] = min(dp[i, j], dp[i, j-v[i]] + w[i])

answer = 0
for i in range(N*V+1):
    if dp[N, i] <= W:
        answer = i

print(answer)

Submission status: Time Limit Exceeded

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

dp=[float("inf")]*(10**5+1)
dp[0]=0
for i in range(n):
  for j in range(10**5,A[i][1]-1,-1):
    dp[j]=min(dp[j],dp[j-A[i][1]]+A[i][0])
ans=0
for v,e in enumerate(dp):
  if e<=w:
    ans=v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)
max_v = N*sum(v)
dp = [INF]*(max_v+1)
dp[0] = 0
for i in range(N):
	for j in range(max_v-v[i], -1, -1):
		dp[j+v[i]] = min(dp[j+v[i]], dp[j]+w[i])

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)
max_v = N*sum(v)
dp = [INF]*(max_v+1)
dp[0] = 0
for i in range(N):
	for j in range(max_v, -1, -1):
		if j-v[i] >= 0:
			dp[j] = min(dp[j], dp[j-v[i]]+w[i])

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)
max_v = N*sum(v)
dp = [INF]*(max_v+1)
dp[0] = 0
for w, v in zip(w, v):
	for i in range(max_v, -1, -1):
		if i-v >= 0:
			dp[i] = min(dp[i], dp[i-v]+w)

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)
max_v = N*sum(v)
dp = [INF]*(max_v+1)
dp[0] = 0
for w, v in zip(w, v):
	for i in range(max_v, -1, -1):
		if i-v >= 0:
			dp[i] = min(dp[i], dp[i-v]+w)

ans = 0
for i in range(len(dp)):
	if dp[i] <= W:
		ans = max(ans, i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
a = []
p = []
for i in range(n):
    k,v = map(int,input().split())
    a.append(v)
    p.append(k)


if sum(p) <= w:
    print(sum(a))
    exit()

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

    dp.append(o)


for i in range(0,n):
    for j in range(0,w+1):
        if p[i] > j:
            dp[i+1][j] = dp[i][j]

        else:
            dp[i+1][j] = max(a[i] + dp[i][j - p[i]], dp[i][j])

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W+1)] for x in range(n+1)] 
  
    # Build table K[][] in bottom up manner 
    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] 
  
    return K[n][W] 
n,w=map(int,input().split())

wt = []
val = []

for i in range(n):
    wtt,vall=map(int,input().split())
    wt.append(wtt)
    val.append(vall)
ans = knapSack(w,wt,val,n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n,w = li()
l = []
for i in range(n):l.append(li())
l.sort()
d = defaultdict(int)
for i in l:

    for j in sorted(list(d),reverse=1):
        if j + i[0] <= w:
            d[j + i[0]] = max(d[j + i[0]],d[j] + i[1])
    d[i[0]] = max(d[i[0]],i[1])
print(max(d.values()))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout

input = stdin.readline
print = stdout.write

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

inf= 1e18+5
mx = 1000* n
dp = [inf for x in range(w+1)] *(mx+ 1)

dp[0] = 0

for _ in range(n):
    x,y = map(int,input().split())
    for i in range(mx-y,-1,-1):
        dp[i+y] = min(dp[i+y],dp[i]+x)

for i in range(mx,-1,-1):
    if dp[i] <= w:
        print(str(i))
        break

Submission status: Time Limit Exceeded

Solution code:
def submit():
    n, w = map(int, input().split())
    item_max = 100
    val_max = 1000
    col_max = item_max * val_max
 
    # dp[i][j] = item iまでで価値jになるようにした時の最小重み
    dp = [[float('inf') for _ in range(col_max + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 0

    for i in range(1, n + 1):
        wi, vi = map(int, input().split())
        for j in range(col_max + 1):
            if 0 <= j - vi <= col_max:
                dp[i][j] = min(dp[i - 1][j],
                               dp[i - 1][j - vi] + wi)
            else:
                dp[i][j] = dp[i - 1][j]

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

submit()

Submission status: Time Limit Exceeded

Solution code:
def rec(n,s):
    if n==0:
        return 0
    if s in dp[n]:
        return dp[n][s]
    else:
        if wt[n-1]>s:
            dp[n][s]=rec(n-1,s)
            return dp[n][s]
        else:
            dp[n][s]=max(val[n-1]+rec(n-1,s-wt[n-1]),rec(n-1,s))
            return dp[n][s]
          
n,w=map(int,input().split())
val=[]
wt=[]
for i in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    val.append(b)
dp=[{} for i in range(n+1)]
print(rec(n,w))

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
oj=[]
for i in range(N):
  oj.append(list(map(int,input().split())))
M=100*1001
dp=[10**10]*M
dp[0]=0
for i in range(N):
  for j in range(M,-1,-1):
    if j+oj[i][1]<M:
      k=j+oj[i][1]
      dp[k]=min(dp[k],dp[j]+oj[i][0])
v=0
for i in range(M):
  if dp[i]<=W:v=i
print(v)

Submission status: Time Limit Exceeded

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

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

for i in range(n+1):
    if i == 0:
        continue
    for j in range(weight+1):
        case1 = dp[i-1][j]
        if j - items[i-1][0] < 0:
            dp[i][j] = case1
            continue
        else:
            case2 = dp[i-1][j-items[i-1][0]] + items[i-1][1]
            if case1 >= case2:
                dp[i][j] = case1
            else:
                dp[i][j] = case2

print(dp[n][weight])

Submission status: Time Limit Exceeded

Solution code:
def rr(): return input().rstrip()
def rri(): return int(rr())
def rrl(): return list(map(int, rr().split()))
def rrt(): return tuple(map(int, rr().split()))
from collections import defaultdict
def mus(d=lambda: 0): return defaultdict(lambda: defaultdict(d))
def dd0(d=lambda: 0): return defaultdict(d)
def ms(x, y, d=0): return [[0]*y for i in range(x)]
def ar(x, d=0): return [d]*x
def ppm(m, n=0, x=0, y=0): print("\n".join(("\t".join((str(m[j][i]) for j in range(y or n))) for i in range(x or n))))
def ppa(a, n): print("\t".join(map(str, a[0:n])))
def ppl(a=0, x=[1]): x[0]=a or (x[0]+1); print("-"+"- -"*14+"-# "+str(x[0]-2)+" #-"+"- -"*14+"-")
def fltn(a): (i for sub in a for i in sub)
def yn(x): return "YES" if x else "NO"
from itertools import accumulate
from itertools import groupby
def grp(x): return ((i, sum(1 for _ in g)) for i, g in groupby(x))
import math
#def rnar(): return (*rrl(), rrl())
#def rn(): return (*rrl(),)
def dpp(a, b=""): print(")#| {} |#(o) ? {} ? (".format(a, b))

def read():
    n, w = rrl()
    l = [rrt() for _ in range(n)]

    return n, w, l

def solve(n, w, l):
    dp = ms(w+1, n+1)

    for wi in range(1, w+1):
        for ii in range(1, n+1):
            if l[ii-1][0] > wi:
                dp[wi][ii] = dp[wi][ii-1]
            else:
                dp[wi][ii] = max(
                        dp[wi][ii-1],
                        dp[wi-l[ii-1][0]][ii-1] + l[ii-1][1],
                        )
    #ppm(dp, w+1, n+1)

    ans = dp[w][n]
    return ans

if __name__ == "__main__":
    #test_count = rri()
    test_count = 1
    for _ in range(test_count):
        input_data = read()
        result = solve(*input_data)
        print(result)

Submission status: Time Limit Exceeded

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

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

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

ans = 0
for j in range(1, MAX):
    if dp[-1][j] <= W:
        ans = j

print(ans)

Submission status: Time Limit Exceeded

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

    weights = []
    values = []
    for i in range(N):
        wi, vi =map(int, input().split())
        weights.append(wi)
        values.append(vi)

    sum_v = sum(values)

    INF = 10**9+7

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


    for i in range(N):
        wi = weights[i]
        vi = values[i]
        for j in range(sum_v+1):
            if j < vi:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-vi]+ wi)

    for j in range(sum_v+1):
        if dp[N][j] <= W:
            ans = j

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, W =map(int, raw_input().split())

    weights = []
    values = []
    for i in range(N):
        wi, vi =map(int, raw_input().split())
        weights.append(wi)
        values.append(vi)

    sum_v = sum(values)

    INF = 10**9+7

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


    for i in range(N):
        wi = weights[i]
        vi = values[i]
        for j in range(sum_v+1):
            if j < vi:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-vi]+ wi)

    for j in range(sum_v+1):
        if dp[N][j] <= W:
            ans = j

    print ans

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

weights = []
values = []
for i in range(N):
    wi, vi =map(int, raw_input().split())
    weights.append(wi)
    values.append(vi)

sum_v = sum(values)

INF = 10**9+7

dp = [[INF]*(sum_v+1) for _ in range(N+1)]
dp[0][0] = 0
#dp[0][values[0]] = weights[0]                                                                                         


for i in range(N):
    wi = weights[i]
    vi = values[i]
    for j in range(sum_v+1):
        if j < vi:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-vi]+ wi)

for j in range(sum_v+1):
    if dp[N][j] <= W:
        ans = j

print ans

Submission status: Time Limit Exceeded

Solution code:
n,W = list(map(int,input().split()))
w_v_list = [list(map(int,input().split())) for i in range(n)]
w_list = [w_v_list[i][0] for i in range(n)] #1番荷物～n番荷物の重さリスト
v_list = [w_v_list[i][1] for i in range(n)] #1番荷物～n番荷物の価値リスト

# dp用の空行列（[0～W]×[0～n]の行列）
dp = [[0 for i in range(W+1)] for j in range(n+1)]

# 「1番荷物(i=0)」......「n番荷物(i=n-1)」から何番目までを使うかの場合分け
# 仮に重量制限が「0」「1」......「W」だった場合の場合分け
for i in range(n):
    for j in range(W+1):
        if w_list[i] > j: # もしi番目の重さが重量制限を超えている場合
            dp[i+1][j] = dp[i][j]
        else: # 重量制限の残り「j-w_list[i]」を重量制限としてdpから引用してdp更新
            dp[i+1][j] = max(dp[i][j],dp[i][j-w_list[i]]+v_list[i])

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