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:
from functools import lru_cache 
n,W = map(int,input().split())
w,p = [],[]
for i in range(n):
    a,b = map(int,input().split())
    w.append(a)
    p.append(b)
@lru_cache(None)
def knapsack(W,i):
    if W==0 or i<0:
        return 0
    if w[i]>W:
        return knapsack(W,i-1)
    return max(knapsack(W,i-1),p[i]+knapsack(W-w[i],i-1))
print(knapsack(W,n-1))

Submission status: Time Limit Exceeded

Solution code:
import sys

N, W = map(int, input().split())
WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

INF = 10**10 + 1
dp = [[INF]*(N+1) for i in range(1000*N+2)]

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

i = 1

while(True):
        for j in range(1, N+1):
                if i-WV[j-1][1]>=0:
                        dp[i][j] = min(dp[i-WV[j-1][1]][j-1]+WV[j-1][0], dp[i][j-1])
                else:
                        dp[i][j] = min(dp[i][j-1], WV[j-1][0])
        #print(i, dp[i][N])
        if dp[i-1][N] <= W and dp[i][N] > W:
                break
        i += 1

print(i-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce


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


def iinput():
    return int(input())


def tinput():
    return input().split()


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))


# ----------------------------------------------------

if __name__ == "__main__":
    n, weigh = rinput()
    w, v = [], []
    for i in range(n):
        wi, vi = rinput()
        w.append(wi)
        v.append(vi)

    mxv = sum(v)
    dp = [[float('inf') for i in range(mxv+1)]for j in range(n+1)]
    for i in range(n+1):
        dp[i][0]=0
    # print(w_v)
    for item in range(1, n+1):
        for val in range(1, mxv+1):
            if v[item-1] <= val:
                dp[item][val] = min(
                    dp[item-1][val-v[item-1]]+w[item-1], dp[item-1][val])
            else:
                dp[item][val] = dp[item-1][val]
    # print(dp)
    ans=float('inf')
    for i in range(mxv,0,-1):
        if dp[n][i]<=weigh:
            ans=i
            break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce


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


def iinput():
    return int(input())


def tinput():
    return input().split()


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))


# ----------------------------------------------------


def solve(item, weight):
    if weight < 0:
        return -9999999999999999999
    if item == 0:
        return 0

    # print(item, weight)
    if dp[item][weight] != -1:
        # print('hello')
        return dp[item][weight]

    solution1 = solve(item-1, weight)
    solution2 = solve(item-1, weight-w_v[item-1][0])+w_v[item-1][1]
    # print(solution1,solution2)
    dp[item][weight] = max(solution1, solution2)
    # print(dp[item][weight])
    return dp[item][weight]


if __name__ == "__main__":
    n, w = rinput()
    w_v = []
    for i in range(n):
        w_v.append(rlinput())
    dp = [[-1 for i in range(w+1)]for j in range(n+1)]
    print(solve(n, w))
    # print(dp)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce


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


def iinput():
    return int(input())


def tinput():
    return input().split()


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))


# ----------------------------------------------------

if __name__ == "__main__":
    n, w = rinput()
    w_v = []
    for i in range(n):
        w_v.append(rlinput())
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    # print(w_v)
    for item in range(1, n+1):
        for weight in range(1, w+1):
            if weight >= w_v[item-1][0]:
                dp[item][weight] = max(dp[item-1][weight-w_v[item-1][0]]+w_v[item-1][1],dp[item-1][weight])
            else:
                dp[item][weight] =dp[item-1][weight]
    print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
max_V = 100010
N,W = map(int, input().split())
lis = [[float('inf')] *(max_V) for _ in range(N+1)]
lis[0][0] = 0 #初期条件の入力が必要　Edu_Dでは初期化とともに初期条件入力済んでいたがこれは違う
item = []
for i in range(N):
    w,v = map(int, input().split())
    item.append((w,v))
for i in range(1,N+1):
    for j in range(max_V):
        lis[i][j] = min(lis[i-1][j], (lis[i-1][j-item[i-1][1]] + item[i-1][0]))
ans = 0
for i in range(N+1):
    for j in range(max_V):
        if lis[i][j] <= W:
            ans = max(j, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, w = list(map(int, input().split(' ')))

wvs = [None] * n
for i in range(n):
    wvs[i] = (list(map(int, input().split(' '))))

INF = float('inf')
max_v = 10**5 + 100


dp = [[INF] * max_v for _ in range(n + 1)]

dp[0][0] = 0


for i in range(n):
    for v in range(0, max_v):

        if v - wvs[i][1] >= 0:
            dp[i + 1][v] = min([
                dp[i + 1][v],
                dp[i][v - wvs[i][1]] + wvs[i][0]
            ])

        dp[i + 1][v] = min([
            dp[i + 1][v],
            dp[i][v],
        ])

res = 0
for i in range(1, max_v):
    if dp[n][i] <= w:
        res = i
print(res)

Submission status: Time Limit Exceeded

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

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

for i in range(1, n+1):
  for j in range(1, w+1):
    if j < nums[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1][0]] + nums[i-1][1])
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

inf = 10 ** 10
dp = [[inf] * (10**5+3) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    weight, value = map(int, input().split())
    for j in range(10**5 + 3):
        if j - value >= 0:
            dp[i+1][j] = min(
                dp[i][j - value] + weight,
                dp[i][j]
            )
        else:
            dp[i+1][j] = dp[i][j]
for i in reversed(range(10**5+3)):
    if dp[n][i] <= w:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
def KnapSack(val, wt, n, W): 
      
    # matrix to store final result  
    mat = [[0 for i in range(W + 1)]  
              for i in range(2)] 
    # iterate through all items  
    i = 0
    while i < n: # one by one traverse  
                 # each element  
        j = 0 # traverse all weights j <= W 
          
        # if i is odd that mean till  
        # now we have odd number of  
        # elements so we store result   
        # in 1th indexed row  
        if i % 2 == 0: 
            while j < W: # check for each value  
                j += 1
                if wt[i] <= j: # include element  
                    mat[1][j] = max(val[i] + mat[0][j - 
                                     wt[i]], mat[0][j]) 
                else: # exclude element 
                    mat[1][j] = mat[0][j] 
                      
        # if i is even that mean till  
        # now we have even number  
        # of elements so we store  
        # result in 0th indexed row  
        else: 
            while j < W: 
                j += 1
                if wt[i] <= j: 
                    mat[0][j] = max(val[i] + mat[1][j - 
                                     wt[i]], mat[1][j]) 
                else: 
                    mat[0][j] = mat[1][j] 
        i += 1
    # Return mat[0][W] if n is  
    # odd, else mat[1][W]  
    if n % 2 == 0: 
        return mat[0][W] 
    else: 
        return mat[1][W] 
  
# Driver code
n,W = map(int,input().split())
val = [] 
wt = []  
for i in range(n):
    a,b = map(int,input().split())
    val.append(b)
    wt.append(a)
    
print(KnapSack(val, wt, n, W))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
l = []
for i in range(N):
  L = list(map(int, input().split()))
  l.append(L)
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
  for j in range(W+1):
    if j >= l[i-1][0]:
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-l[i-1][0]]+l[i-1][1])
    else:
      dp[i][j] = dp[i-1][j]
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
l=[]
for _ in range(N):
  L=list(map(int,input().split()))
  l.append(L)
dp=[[0 for i in range(W+1)] for i in range(N+1)]
for i in range(1,N+1):
  for j in range(W+1):
    if j>=l[i-1][0]:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-l[i-1][0]]+l[i-1][1])
    else:dp[i][j]=dp[i-1][j]
print(dp[N][W])

Submission status: Time Limit Exceeded

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

    Wi, Vi = [], []
    for _ in range(N):
        w, v = tuple(map(int, input().split()))
        Wi.append(w)
        Vi.append(v)

    # print(N, W)
    # print(Wi, Vi)

    return N, W, Wi, Vi


def solve(N, W, Wi, Vi):
    if N == 1:
        return Vi[0]

    x, y = N + 1, max(Vi) * N + 1
    DP = [[float("inf") for _ in range(y)] for _ in range(x)]

    # print(len(DP[0]))

    DP[0][0] = 0

    for i in range(N):
        value = Vi[i]
        w_max = max(Vi) * N
        for v in range(w_max):
            remain = v - value
            if 0 <= remain:
                # 選ぶ
                DP[i + 1][v] = min(DP[i + 1][v], DP[i][remain] + Wi[i])
            # 選ばない
            DP[i + 1][v] = min(DP[i + 1][v], DP[i][v])

    # print(DP)
    ans = 0
    for line in DP:
        for v, e in enumerate(line):
            if not e == float("inf") and e <= W:
                # print(v, e)
                ans = max(ans, v)

    # print(DP)

    return ans


if __name__ == '__main__':
    res = solve(*args())
    print(res)

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
w = []
v = []
for _ in range(N):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)
dp = [[10000000000000 for _ in range(100 * W + 10)] for _ in range(110) ]
ans = 0
for i in range(N):
    dp[i][0] = 0
for i in range(N):
    for j in range(N * 100):
        dp[i + 1][j + v[i]] = min(dp[i+1][j+v[i]],dp[i][j]+w[i])
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
for i in range(N * 100 + 1):
    if dp[N][i] <= W:
        ans = max(ans,i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,w = list(map(int,input().split()))
mat = [[0 for i in range(w+1)]for j in range(n+1)]
arr = []
for i in range(n):
	arr.append(list(map(int,input().split())))
for i in range(1,n+1):
	wt,val = arr[i-1][0],arr[i-1][1]
	for j in range(1,w+1):
		if j<wt:
			mat[i][j] = mat[i-1][j]
		else:
			mat[i][j] = max(mat[i-1][j-wt]+val,mat[i-1][j])
print(mat[n][w])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)
f = [10**9 for x in range(X + 1)]
f[0] = 0
for n in range(N):
    f = [
        min(f[x], f[x - V[n]] + W[n]) if x >= V[n] else f[x]
        for x in range(X + 1)
    ]
for x in range(X + 1)[::-1]:
    if f[x] <= M:
        print(x)
        exit()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)
# f[n][x] = n番目までの品物でx以上の価値に必要な最小の重さ
f = [[10**9 for x in range(X + 1)] for n in range(N + 1)]
f[0][0] = 0
for n in range(1, N + 1):
    for x in range(X + 1):
        if x >= V[n - 1]:
            f[n][x] = min(f[n - 1][x], f[n - 1][x - V[n - 1]] + W[n - 1])
        else:
            f[n][x] = f[n - 1][x]
ans = X
while f[N][ans] > M:
    ans = ans - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f(n, m):
    if n < 1 or m < 1:
        return 0
    elif m < W[n - 1]:
        return f(n - 1, m)
    else:
        return max(f(n - 1, m), f(n - 1, m - W[n - 1]) + V[n - 1])


N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
print(f(N, M))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
import numpy as np

def resolve():
    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()) 

    sum_v = sum(v)

    # dp[i][j]: 0〜(i-1)まで使ったときの価値jのときの重みの総和の最小値
    dp = [[np.inf]*(sum_v+1) for i in range(N+1)]
    dp[0][0] = 0

    for i in range(1, N+1):
        for j in range(sum_v+1):
            if j-v[i-1] >= 0:
                dp[i][j] = min(dp[i-1][j-v[i-1]] + w[i-1], dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]

    print(max([i for i, w in enumerate(dp[N]) if w<=W]))

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n, W = list(map(int,input().split()))
w_v = [list(map(int,input().split())) for i in range(n)]
w = [w_v[i][0] for i in range(n)]
v = [w_v[i][1] for i in range(n)]
inf = 10**9+1
dp = [[inf] * (sum(v)+1) for i in range(n+1)]
dp[0][0] = 0

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

    dp[i+1][j] = min(dp[i+1][j], dp[i][j])


for i in range(sum(v)+1):
  if dp[n][i] > W:
    pass
  else:
    ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, W = list(map(int,input().split()))
w_v = [list(map(int,input().split())) for i in range(n)]
w = [w_v[i][0] for i in range(n)]
v = [w_v[i][1] for i in range(n)]
inf = 10**9+1
dp = [[inf] * (sum(v)+1) for i in range(n+1)]
#dp = np.zeros((n+1,sum(v)+1),dtype=np.int32)
dp[0][0] = 0

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

    dp[i+1][j] = min(dp[i+1][j], dp[i][j])


for i in range(sum(v)+1):
  if dp[n][i] > W:
    pass
  else:
    ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
w = {}
v = {}

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

dp = {}
dp[0] = {}

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 22 22:30:30 2020

@author: matha
"""

#global


def dp(pos, cw):
    if pos>= N or cw > W:
        return 0;
    
    temp = mem.get((pos, cw), None)
    if temp:
        return temp
    
    w = rec[pos][0]
    
    v1 = 0
    v2 = 0
    
    if(cw+w <= W):
        v1 = rec[pos][1]
        v1 += dp(pos+1, cw + w)
    
    v2 = dp(pos+1, cw)
    
    if(v1>v2):
        mem[(pos, cw)] = v1
        return v1
    else:
        mem[(pos, cw)] = v2
        return v2

rec = []
mem = {}

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

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

print(dp(0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,W = map(int,input().split())
wt =[];val=[]

dp = [[0 for i in range(W+1)] for j in range(n)]
for _ in range(n):
  wi , vi= map(int,input().split())
  wt.append(wi)
  val.append(vi)

for i in range(W+1):
  if i>=wt[0]:
    dp[0][i]=val[0]   
  else:
    dp[0][i]=0
    
    
    
#print(dp)  
for i in range(1,n):
  wi = wt[i]
  vi = val[i]
  for w in range(1,W+1):
    if wi <= w:
      dp[i][w] = max(vi + dp[i-1][w-wi] , dp[i-1][w] )
    else:
      dp[i][w] = dp[i-1][w]

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

Submission status: Time Limit Exceeded

Solution code:
n,W = map(int,input().split())
wt =[];val=[]

dp = [[0 for i in range(W+1)] for j in range(n)]
for _ in range(n):
  wi , vi= map(int,input().split())
  wt.append(wi)
  val.append(vi)

for i in range(W+1):
  if i>=wt[0]:
    dp[0][i]=val[0]   
  else:
    dp[0][i]=0
    
    
    
#print(dp)  
for i in range(1,n):
  wi = wt[i]
  vi = val[i]
  for w in range(1,W+1):
    if wi <= w:
      dp[i][w] = max(vi + dp[i-1][w-wi] , dp[i-1][w] )
    else:
      dp[i][w] = dp[i-1][w]

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

Submission status: Time Limit Exceeded

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

K = [[0 for x in range(W+1)] for y in range(N+1)]

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:
#			print("ayo")
			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])

Submission status: Time Limit Exceeded

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

from collections import Counter

dp = Counter()
dp[0] = 0
for w, v in WV:
  ndp = Counter()
  for k in dp:
   	ndp[k] = max(dp[k], ndp[k])
   	if k+w <= W:
   	 	ndp[k+w] = max(dp[k] + v, ndp[k+w])
  dp = ndp
print(dp.most_common()[0][1])

Submission status: Time Limit Exceeded

Solution code:
def main2():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = [[W+1]*(1000*N+1) for i in range(N+1)] #valueの最大値は10**3なので全てが10**3でも入るような配列を用意．
    #print(*dp,sep="\n")

    #2:初期値(dp[0][0]だけだと結果が合わない)
    for i in range(N+1):
        dp[i][0] = 0

    #3:dp実行部(貰うDP)
    for i in range(1,N+1):
        for j in range(1,1000*N+1):
            if wv[i-1][1] <= j: #dpの横が重さだが，jが重さ以下ならそもそも入れられない．
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-wv[i-1][1]]+wv[i-1][0])
            else:
                dp[i][j] = dp[i-1][j]
            #print(i,j)
            #print(*dp,sep="\n")

    #4:出力
    #print(*dp,sep="\n")
    output = 0
    for i in range(1000*N+1):
        if dp[N][i] <= W:
            output = i
    print(output)

if __name__ == '__main__':
    main2()

Submission status: Time Limit Exceeded

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

INF = 10 ** 18

N, W = map(int, input().split())
lst = [INF] * (10 **5 + 10)
lst[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for i in range(10 ** 5 + 9, v - 1, -1):
        lst[i] = min(lst[i], lst[i - v] + w)
    for i in range(v - 1, -1, -1):
        lst[i] = min(lst[i], lst[i + 1])

for i in range(10 ** 5 + 9, -1, -1):
    if lst[i] <= W:
        print (i)
        exit()

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 9 + 7
N, W = map(int, input().split())
weight = []
value = []
for i in range(N):
    tempW, tempV = map(int, input().split())
    weight.append(tempW)
    value.append(tempV)

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

for i in range(1, N + 1):
    for l in range(N * 1000 + 1):
        if l - value[i - 1] >= 0:
            dp[i][l] = min(dp[i - 1][l], dp[i - 1][l - value[i - 1]] + weight[i - 1])
        else:
            dp[i][l] = dp[i - 1][l]
for i in range(N * 1000 + 1):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = map(int, input().split())
wv = []
sum_v = 0
for i in range(N):
    w,v = map(int, input().split())
    wv.append([w,v])
    sum_v += v
#価値の合計がｖの時の重さの合計の最小値を記録する
dp = np.zeros((N,sum_v+1))
for i in range(N):
    for j in range(1,sum_v+1):
        dp[i][j] = np.inf
        if j == wv[i][1]:
            dp[i][j] = wv[i][0]
    dp[i][0] = 0

for i in range(N):
    w = wv[i][0]
    v = wv[i][1] 
    for j in range(v,sum_v):
        dp[i,j] = min(dp[i-1,j-v]+w,dp[i-1,j])
    
for i in range(sum_v):
    if dp[N-1][-i-1] <= W:
        print(sum_v-i)
        break
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)
MAX_VALUE = sum(value for (weight, value) in WEIGHTS)
 
INF = sys.maxsize
DP = [[INF for _ in range(MAX_VALUE + 1)] for _ in range(M + 1)]
 
for i, (weight, value) in enumerate(WEIGHTS):
    for v in range(MAX_VALUE + 1):
        if v - value >= 0:
            DP[i+1][v] = min(DP[i][v - value] + weight, DP[i][v])
        else:
            DP[i+1][v] = min(DP[i][v], weight)
 
res = 0
for v, w in enumerate(DP[M]):
    if w <= W:
        res = max(res, v)
 
print(res + 1)
 
# dp_ij := 1~jまでのアイテムからいくつかを選んで総価値iを超えないようにしたときの最少重量

Submission status: Time Limit Exceeded

Solution code:
n, w = [int(i) for i in input().split(" ")]
value, weight = [], []
for i in range(n):
  vw= [int(i) for i in input().split(" ")]
  value.append(vw[1])
  weight.append(vw[0])

maxV = sum(value)*n+1
dp = [[float("inf") for j in range(maxV+1)] for i in range(n+1)]
dp[0][0] = 0 
for i in range(n):
  for j in range(maxV):
    if j - value[i] >= 0:
      dp[i+1][j] = min(dp[i][j], dp[i][j - value[i]] + weight[i])
    else :
      dp[i+1][j] = dp[i][j]
    
result = 0
for i in range(maxV):
  if dp[n][i] <= w:
    result = i
print(result)

Submission status: Time Limit Exceeded

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

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

for item in range(n):
    now_w=wv[item][0]
    now_v=wv[item][1]

    for weight in range(w+1):
        ans1=dp[item][weight]
        ans2=-1
        if weight - now_w >= 0:
            ans2=dp[item][weight-now_w]+now_v
        dp[item+1][weight] = max(ans1,ans2)

print(dp[n][w])

Submission status: Time Limit Exceeded

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


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    maxv=sum(v)+1
    dp=[[2**60]*maxv for _ in range(N+1)]
    dp[0][0]=0
    for i in range(N):
        for j in range(maxv):
            if j>=v[i]:
                dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
            else:
                dp[i+1][j]=dp[i][j]

    ans=0
    for j in range(maxv):
        if W >= dp[N][j]:
            ans=j
    print(ans)
    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:
#!/usr/bin/env python3
# Knapsack問題

# input
N,W = map(int, input().split())
w = []
v = []
for _ in range(N):
    a,b = map(int ,input().split())
    w.append(a)
    v.append(b)

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]


def dfs(pos, value, weight):
    if pos == n:
        return value
    if W - weight >= wv[pos][0]:
        ret1 = dfs(pos + 1, value + wv[pos][1], weight + wv[pos][0])
    else:
        ret1 = 0
    ret2 = dfs(pos + 1, value, weight)

    return max(ret1, ret2)


print(dfs(0, 0, 0))

Submission status: Time Limit Exceeded

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


def dfs(pos, value, weight):
    if pos == n:
        if weight <= W:
            return value
        else:
            return 0
    ret1 = dfs(pos + 1, value + wv[pos][1], weight + wv[pos][0])
    ret2 = dfs(pos + 1, value, weight)

    return max(ret1, ret2)


print(dfs(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
N,W = [int(i) for i in input().rstrip().split()]
F = [[int(i) for i in input().rstrip().split()] for _ in range(N)]
 
def dp(f,w):
    global F
    if w < 0:
        return -10**9
    if f == 0:
        if w < F[0][0]:
            return 0
        else:
            return F[0][1]
    return max(dp(f-1,w),dp(f-1,w-F[f][0])+F[f][1])
 
print(dp(N-1,W))

Submission status: Time Limit Exceeded

Solution code:
# W <= 10^9になったことに注意．
N, WW = map(int, input().split())
W, V = [], []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = {(0, 0)}
for wi, vi in zip(W, V):
    newset = {(w+wi, v+vi) for w, v in dp}
    dp |= newset
    
res = 0
for totw, totv in dp:
    if totw > WW:
        continue
    res = max(res, totv)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import namedtuple

INF = sys.maxsize

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

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

items = []

for _ in range(N):
  w, v = map(int, input().split())
  items.append(Item(w, v))
  
memo = [0] + [INF] * 100000
  
for item in items:
  for v in range(100000, item.v - 1, -1):
    memo[v] = min(memo[v], memo[v - item.v] + item.w)

print(max([v for v, w in enumerate(memo) if w <= W]))

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    for j in range(w[i]-1,W):
        dp[i][j] = v[i]

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

Submission status: Time Limit Exceeded

Solution code:
n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
vmax = max(wv, key=lambda x:x[1])[1]
dp = [[float('inf')] * (n * vmax + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(0, n * vmax + 1):
        if j - wv[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wv[i][1]] + wv[i][0])
        else:
            dp[i][j] = dp[i - 1][j]
for i in range(n * vmax, -1, -1):
    if dp[n][i] <= w:
        ans = i
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
vmax = max(wv, key=lambda x:x[1])[1]
dp = [[float('inf')] * (n * vmax + 1) for _ in range(n + 1)]
for i in range(w + 1):
    dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(0, n * vmax + 1):
        if j - wv[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wv[i][1]] + wv[i][0])
        else:
            dp[i][j] = dp[i - 1][j]
for i in range(n * vmax, -1, -1):
    if dp[n][i] <= w:
        ans = i
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
vmax = max(wv, key=lambda x:x[1])[1]
dp = [[float('inf')] * (n * vmax + 1) for _ in range(n + 1)]
for i in range(w + 1):
    dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(0, n * vmax + 1):
        if j - wv[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wv[i][1]] + wv[i][0])
        else:
            dp[i][j] = dp[i - 1][j]
ans = 0
for i in range(n * vmax, -1, -1):
    if dp[n][i] <= w:
        ans = i
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,W = [int(i) for i in input().split()]
dp = [0 for i in range(W+1)] # dp[i] is the the max value you have achieve with weight i
for i in range(N):
  w,value = [int(i) for i in input().split()]
  for weight in range(W-w, -1, -1): # range of kanpsack weight in which i can push the current item
    dp[weight + w] = max(dp[weight + w], dp[weight] + value)
print("%s" % dp[W])