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:
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=limit_w<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF = 2000000000
"""
メモ : Pythonでは無限大を表す float('inf') があるが, 処理がかなり重たいので
       代わりにsum(v)より真に大きい 2*10^9 を INFとする.
       (https://atcoder.jp/contests/dp/tasks/dp_e において,PyPyを使用して,
        前者だと1060ms, 後者だと570msで2倍近く差が出ている.)
"""
n ,limit_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 = [INF for i in range(sum_v + 1)]
# dp[i][j]には重さが入る.
# dp[i][j]=(i番目までの品物から価値がちょうどｊになるための重さの最小値)

# ここからメイン
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])

# n個まで使って,重さがlimit_wを超えないで価値が最大のものを求める.
ans = 0
for i in range(sum_v + 1):
    if dp[i] <= limit_w:
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    w = [0] * n
    v = [0] * n
    for i in range(n):
        w[i], v[i] = list(map(int, input().split()))
    t = sum(v) + 1
    l = [m + 1] * (t + 1) 
    for i in range(n):
        for j in range(t, v[i] - 1, -1):
            k = l[j - v[i]] + w[i]
            if j == v[i] and w[i] < l[j]:
                l[j] = w[i]
            elif k < l[j]:
                l[j] = k
    for i in range(t, 0, -1):
        if l[i] <= m:
            print(i)
            break
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    w = [0] * n
    v = [0] * n
    for i in range(n):
        w[i], v[i] = list(map(int, input().split()))
    t = sum(v) + 1
    l = [float('inf')] * (t + 1) 
    for i in range(n):
        for j in range(t, v[i] - 1, -1):
            if j == v[i]:
                l[j] = min(l[j], w[i])
            elif l[j - v[i]] + w[i] < l[j]:
                l[j] = l[j - v[i]] + w[i]
    for i in range(t, 0, -1):
        if l[i] <= m:
            print(i)
            break
main()

Submission status: Time Limit Exceeded

Solution code:
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF=2*10**9
n,W = map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    x,y = map(int, input().split())
    w[i] = x
    v[i] = y
max_v=max(v)
dp = [[INF for i in range(n*max_v+1)] for j in range(n+1)]

#ここからメイン
dp[0][0]=0
for i in range(n):
    for j in range(n*max_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])
ans=0
for i in range(n*max_v+1):
    if dp[n][i]<=W:
        ans=i
print(ans)

Submission status: Time Limit Exceeded

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

def Main(N, W, V):
    dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            if(j < V[i][0]):
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j], dp[i][j-V[i][0]]+V[i][1])
    return dp[N][W]            

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値(ときどき逆になることがあるので注意)
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return max(dp[-1])
print(knapsack(n,w,li))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
n,W = map(int,input().split())
dp = [10**12] * (10**5+1)
dp[0] = 0
for i in range(n):
  w,v = map(int,input().split())
  pdp = deepcopy(dp)
  for j in range(v,10**5+1):
    dp[j] = min(pdp[j-v]+w,dp[j])
m = 0
for i in range(10**5+1):
  if dp[i] <= W:
    m = i
print(m)

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
items = []
tv = 0
MAX = W+1
for i in range(N):
	items.append(list(map(int, input().split())))
	tv += items[-1][1]
	
dp = [MAX for i in range(tv+1)]
for i, item in enumerate(items):
    for j in range(tv, item[1] - 1, -1):
        if j != item[1] and dp[j-item[1]] != MAX:
            dp[j] = min(dp[j], dp[j-item[1]] + item[0])
        elif j == item[1]:
            dp[j] = item[0]
for i in range(tv, -1, -1):
    if dp[i] != MAX:
        print(i)
        break

Submission status: Time Limit Exceeded

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

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

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

for i in reversed(range(n)):
    for j in reversed(range(W)):
        weight, val = w[i], v[i]

        if j + weight <= W:
            chose = dp[i+1][j + weight] + val
            unchose = dp[i+1][j]
            dp[i][j] = max(chose, unchose)
        else:
            dp[i][j] = dp[i+1][j]

#print(*dp)
#print(dp[n][W])

# for i in range(len(dp)):
#     print(dp[i])
print(dp[0][0])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
dp=[[9999999999 for _ in range((1000)*n + 1)] for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
    wi,vi=map(int,input().split())
    for j in range((1000)*n+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 i in range((1000)*n + 1):
    if(dp[n][(1000)*n - i] <= w):
        print((1000)*n - i)
        break

Submission status: Time Limit Exceeded

Solution code:
n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
    left = v if v < 100001 else 100001
    right = left + ans + 1 if left + ans + 1 < 100001 else 100001
    for i in range(left, right)[::-1]:
        mn = bag[i] if bag[i] < W+1 else W + 1
        if bag[i-v] + w < mn:
            bag[i] = bag[i-v] + w
            if i > ans:
                ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
    left = v if v < 100001 else 100001
    right = left + ans + 1 if left + ans + 1 < 100001 else 100001
    for i in range(left, right)[::-1]:
        if bag[i-v] + w < min(bag[i],W+1):
            bag[i] = bag[i-v] + w
            if i > ans:
                ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
  for i in range(min(v,10**5+1), 10**5+1)[::-1]:
    if bag[i-v] + w < min(bag[i],W+1):
        bag[i] = bag[i-v] + w
        if i > ans:
          ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
  for i in range(min(v,10**5+1), 10**5+1)[::-1]:
    if bag[i-v] + w < min(bag[i],W+1):
        bag[i] = bag[i-v] + w
        ans = max(ans, i)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
v_max = 100010
INF = 1000000100
n, w = map(int, input().split())
weight = [0]*n
value = [0]*n
dp = [[INF for i in range(v_max+1)] for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
    weight[i], value[i] = map(int, input().split())

for i in range(n):
    for j in range(v_max+1):
        if j - value[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j - value[i]] + weight[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

result = 0
for j in range(v_max+1):
    # print("v_sum: " + str(j) + " , weight: " + str(dp[n][j]))
    if dp[n][j] <= w:
        result = j
print(result)

Submission status: Time Limit Exceeded

Solution code:
import copy

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




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


for i in range(W+1):
    if i < w[0]:
        s[0][i] = 0
    else :
        s[0][i] = v[0]

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

Submission status: Time Limit Exceeded

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

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

for j in range(Vmax):
    if 0<=dp[N][j]<=W:
        ans = max(ans,j)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,w=list(map(int, input().split()))
wv =[]
sum_w = 0
sum_v = 0
for i in range(n):
    wv_1 = list(map(int, input().split()))
    wv.append(wv_1)
    sum_w += wv_1[0]
    sum_v += wv_1[1]

dp = [[float("inf") for _ in  range(sum_v+1)] for _ in range(n+1)]
dp[0][0] = 0

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

for i,name in enumerate(dp[n][::-1]):
    if name <= w:
        break

print(sum_v - i)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

N,W = MAP()
weight=[]
value=[]
for i in range(N):
    w,v = MAP()
    weight.append(w)
    value.append(v)
MAX_V = 100100

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

for i in range(N):
    for sum_v in range(MAX_V):
        if sum_v - value[i]>=0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v-value[i]]+weight[i])
        dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v])


for sum_v in range(MAX_V):
    if dp[N][sum_v]<=W:
        res=sum_v
print(res)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
table = []
for i in range(N):
  w,v = map(int, input().split())
  table.append((w,v))
INF = W+1
dp = [[INF]*(10**3*N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  for k in range(10**3*N+1):
    w,v = table[i-1]
    dp[i][k] = dp[i-1][k]
    if v<=k and dp[i-1][k-v] <= INF:
      dp[i][k] = min(dp[i][k],dp[i-1][k-v]+w)

for i in range(10**3*N,-1,-1):
  if 0<= dp[-1][i] <= W:
    print(i)
    exit()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout

N = 100 + 7
V = 100000 + 7

inf = 10**10

dp = [[inf for _ in range(V)] for _ in range(N)]

def knapsack(n: int, W: int, wt: list, val: list) -> int:
	global dp

	for i in range(n):
		dp[i][0] = 0

	dp[0][val[0]] = wt[0]

	for i in range(1,n):
		for value in range(1, V):
			if val[i] > value:
				dp[i][value] = dp[i-1][value]
			else:
				dp[i][value] = min(dp[i-1][value-val[i]] + wt[i], dp[i-1][value])

	for i in range(V-1, -1, -1):
		if dp[n-1][i] <= W:
			return i

	return -1	

def main():
	n, W = list(map(int, stdin.readline().strip().split()))

	wt = []
	val = []

	for _ in range(n):
		w, v = list(map(int, stdin.readline().strip().split()))

		wt.append(w)
		val.append(v)

	stdout.write(str(knapsack(n, W, wt, val)))


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
N = 100 + 7
V = 100000 + 7

inf = 10**10

dp = [[inf for _ in range(V)] for _ in range(N)]

def knapsack(n: int, W: int, wt: list, val: list) -> int:
	global dp

	for i in range(n):
		dp[i][0] = 0

	dp[0][val[0]] = wt[0]

	for i in range(1,n):
		for value in range(1, V):
			if val[i] > value:
				dp[i][value] = dp[i-1][value]
			else:
				dp[i][value] = min(dp[i-1][value-val[i]] + wt[i], dp[i-1][value])

	for i in range(V-1, -1, -1):
		if dp[n-1][i] <= W:
			return i

	return 0	

def main():
	n, W = list(map(int, input().strip().split()))

	wt = []
	val = []

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

		wt.append(w)
		val.append(v)

	print(knapsack(n, W, wt, val))


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)
dp = [{} for i in range(n+1)]

for i in range(n):
    Lw, Lv =L[i][0], L[i][1] #①i番目の価値を重さテーブルに代入
    dp[i+1][Lw] = Lv 
    for w, v in dp[i].items():
        dp[i+1][w] = max(dp[i+1].get(w, 0), v) #② 一つ上の行の価値と比べて大きい方を代入
        if w + Lw <=limit:
            dp[i+1][w+Lw] = max(dp[i].get(w+ Lw, 0), Lv + v) #③一つ上の行の価値をループで1つづつ取り出し、i番目の価値と足し合わせる
        
print(max(dp[-1].values()))

Submission status: Time Limit Exceeded

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

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

#i番目まで選べる時に価値がｊとなる最小の重み
dp = [{} for _ in range(N+1)]
dp[0][0] = 0

for i, (w, v) in enumerate(wv):
    # i番目のアイテムまで選んで作れる価値とその時の最小重さの組を取り出す
    for v0, w0 in dp[i].items():
        # 価値v0になる組み合わせが、i番目までの中から選ぶ中で既に存在しているばあい
        if v0 in dp[i+1]:
            # 軽い方を残す
            dp[i+1][v0] = min(dp[i+1][v0], w0) #同じ価値で重さが違うとか、組み合わせで価値は同じだが重さが違うみたいな場合
        # i番目まで選んだ時に重さw0になる組がない場合
        else:
            # i番目まで使い、i+1番目は使わない
            dp[i+1][v0] = w0
        
        # i番目（重さw）を使って、或る組み合わせの価値＋i番目で重量制限を超えたらアウト
        if w0 + w > W:
            continue
        # 上と同じ感じで、今まで+i番目の価値と同じ価値の組が、既に存在する場合、軽いほうを残す
        if v0 + v in dp[i+1]:
            dp[i+1][v0 + v] = min(dp[i+1][v0 + v], w0 + w)
        else:
            dp[i+1][v0 + v] = w0 + w

#最後まで選べる中で、最も価値が大きいもの（重さがオーバーするものはcontinueで落ちてるから問題ない）
print(max(dp[-1].keys()))

Submission status: Time Limit Exceeded

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

sum_v = sum(v)

dp = [[10**18] * (sum_v + 1) for _ in range(N + 1)]

for i in range(N+1):
    dp[i][0] = 0
    
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
    for j in range(sum_v + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
        if j - v[i] == 0:
            dp[i + 1][j] = min(w[i],dp[i][j])
        if dp[i][j] != 10**18:
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j]+w[i])
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

for i in range(sum_v + 1):
    #print(dp[N][sum_v - i],i)
    if dp[N][sum_v - i] <= W and dp[N][sum_v - i] != 0:
        print(sum_v - i)
        exit()

print(0)

Submission status: Time Limit Exceeded

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

sum_v = sum(v)

dp = [[10**18] * (sum_v + 1) for _ in range(N + 1)]

for i in range(N+1):
    dp[i][0] = 0
    
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
    for j in range(sum_v + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
        if j - v[i] == 0:
            dp[i + 1][j] = min(w[i],dp[i][j])
        if dp[i][j] != 10**18:
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j]+w[i])
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

for i in range(sum_v + 1):
    #print(dp[N][sum_v - i],i)
    if dp[N][sum_v - i] <= W and dp[N][sum_v - i] != 0:
        print(sum_v - i)
        exit()

print(0)

Submission status: Time Limit Exceeded

Solution code:
#DP E
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
m=0
for i in range(n):
    m+=wv[i][1]
inf=float("inf")
dp=[[inf]*(m+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
    w,v=wv[i]
    for j in range(m+1):
        if j<v:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v]+w)
ans=0
for i in range(m+1):
    if dp[n][i]<=W:
        ans=i
print(ans)

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]"):
    dp = [[float('inf') for _ in range(10**5+1)] for _ in range(N)]
    dp[0][0] = 0
    dp[0][v[0]] = w[0]

    js = [0,v[0]]

    for i in range(1,N):
        for j in js[:]:
            js.append(j+v[i])
        js = list(set(js))

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

    res = 0
    for i,j in enumerate(dp[-1]):
        if j != float("inf") and j <= W:
            res = i
    print(res)

    return


# Generated by 1.1.5 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
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[float('inf') for _ in range(10**5+1)] for _ in range(N)]
    dp[0][0] = 0
    dp[0][v[0]] = w[0]

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

    res = 0
    for i,j in enumerate(dp[-1]):
        if j != float("inf") and j <= W:
            res = i
    print(res)

    return


# Generated by 1.1.5 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
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[float('inf') for _ in range(10**5+1)] for _ in range(N)]
    dp[0][0] = 0
    dp[0][v[0]] = w[0]

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

    res = 0
    for i,j in enumerate(dp[-1]):
        if j != float("inf") and j <= W:
            res = i
    print(res)

    return


# Generated by 1.1.5 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
import numpy as np
input = sys.stdin.readline

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

    INF = int(1e20)
    dp = np.array([[INF] * (1000 * N + 1) for i in range(N+1)])
    dp[0][0] = 0

    for i in range(N):
        w, v = wv[i]
        dp[i+1] = dp[i]
        dp[i+1, v:] = np.minimum(dp[i+1, v:], dp[i, :-v] + w)
    
    for i in range(1000, -1, -1):
        if dp[N][i] <= W:
            print(i)
            break

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#from collections import defaultdict
n, limit= map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

#各重さとi番目の荷物を入れ終わった状態のテーブルをつくる
d = {}
dp = [d.copy() for _ in range(n)]

#初期状態
for w in range(L[0][0], limit+1):
    dp[0][w] = L[0][1]
#print(dp)
for i in range(1, n):
    for w in range(1, limit+1):
        if dp[i-1].get(w-L[i][0]) and dp[i-1].get(w): #キーが存在するなら
            dp[i][w] = max(dp[i-1][w-L[i][0]] + L[i][1], dp[i-1][w])
        elif dp[i-1].get(w) and w==L[i][0]:
            dp[i][w] = max(L[i][1], dp[i-1][w])
        elif dp[i-1].get(w):
            dp[i][w] = dp[i-1][w]
        elif w==L[i][0]:
            dp[i][w] = L[1][1]
    #print(dp)  
print(max(dp[-1].values()))

Submission status: Time Limit Exceeded

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

w, v = [], []
MAX_V = 100001
INF = 1000000000001

for i in range(N):
  wi, vi = [int(x) for x in input().split()]
  w.append(wi)
  v.append(vi)

dp = []
for i in range(N+1):
  dp.append([INF] * MAX_V)

dp[0][0] = 0

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


res = 0
for sum_v in range(MAX_V):
  if dp[N][sum_v] <= W:
    res = sum_v
  
print(res)

Submission status: Time Limit Exceeded

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

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

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

print(max(dp[-1]))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
class Solver():
    def __init__(self, N, W, items):
        self.N = N
        self.W = W
        self.items = items

    def solve(self):
        dp = [[0 for _ in range(self.W+1)] for _ in range(self.N+1)]
        for i in range(self.N):
            for w in range(self.W+1):
                if w - self.items[i][0] >= 0:
                    dp[i+1][w] = max(dp[i+1][w], dp[i][w - self.items[i][0]] + self.items[i][1])

                dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        return dp[self.N][self.W]


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

dp = [[float('INF') for i in range(V+1)] for i in range(N+1)]
dp[0][0] = 0

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

ans = V
while dp[N][ans] > W:
    ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
N,W =  map(int, sys.stdin.readline().split())

dp =  [[0 for i in range(W+1)]for j in range(N+1)]#動的計画法の表を作成。
v=[0]*N
w=[0]*N

for i in range(N):
        w[i],v[i] =  map(int, sys.stdin.readline().split())

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

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

Submission status: Time Limit Exceeded

Solution code:
def KnapSack(W,wt,val,n):
    mat = [[0 for i in range(W + 1)]
           for i in range(2)]
    i=0
    while i < n:
        j=0
        if i % 2 == 0:
            while j < W:
                j += 1
                if wt[i] <= j:
                    mat[1][j] = max(val[i] + mat[0][j -
                                                    wt[i]], mat[0][j])
                else:
                    mat[1][j] = mat[0][j]
        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
    if n % 2 == 0:
        return mat[0][W]
    else:
        return mat[1][W]
n, W = map(int, input().split())
wt = []
val = []
for i in range(n):
    a, b = map(int, input().split())
    wt.append(a)
    val.append(b)
print(KnapSack(W, wt, val, n))

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)]
    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):
    a, b = map(int, input().split())
    wt.append(a)
    val.append(b)
print(knapSack(W, wt, val, n))

Submission status: Time Limit Exceeded

Solution code:
def knapSack(W, wt, val, n):
    if n == 0 or W == 0:
        return 0
    if (wt[n - 1] > W):
        return knapSack(W, wt, val, n - 1)
    else:
        return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
                   knapSack(W, wt, val, n - 1))


n, W = map(int, input().split())
wt = []
val = []
for i in range(n):
    a, b = map(int, input().split())
    wt.append(a)
    val.append(b)
print(knapSack(W, wt, val, n))