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:
N, W = map(int, input().split())
items = [None] * N
for n in range(N):
    w, v = map(int, input().split())
    items[n] = (w, v)
V = 10 ** 6 + 1

dp = [[10 ** 9 + 1] * V for _ in range(N + 1)]
dp[0][0] = 0

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

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

Submission status: Time Limit Exceeded

Solution code:
import os, sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")
 
sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10**18
MOD = 10**9 + 7

def N(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))
def bulk_li(): return list(map(lambda s: list(map(int, s.split())), sys.stdin.readlines()))

n, w = li()
wv = bulk_li()

# print(wv)
table = dict()

# 以下の条件で最大の価値の総和を返す
# i番目以降(i+1..n)の品物 / 残重量jのナップサック
def dp(i, j):
    if i == n:
        return 0
    if (i, j) in table:
        return table.get((i, j))

    w, v = wv[i]
    if w > j:
        return dp(i+1, j)

    table[(i, j)] = max(v + dp(i+1, j-w), dp(i+1, j))
    return table[(i, j)]

print(dp(0, w))


"""
TLE
https://atcoder.jp/contests/dp/submissions/6675353

recursionでやると遅い。
"""

Submission status: Time Limit Exceeded

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

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

dp = [[10**10 for i in range(2*10**6)] for j in range(2*N)]
dp[0][0] = 0

for i in range(N):
    for j in range(10**6):
        if j - wv[i][1] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-wv[i][1]]+wv[i][0])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for i in range(10**6):
    if dp[N][i] <= W: 
        ans = i
print(ans)

Submission status: Time Limit Exceeded

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

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

dp = [[10**10 for i in range(2*10**6)] for j in range(2*N)]
dp[0][0] = 0

for i in range(N):
    for j in range(10**6):
        if j - wv[i][1] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-wv[i][1]]+wv[i][0])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for i in range(10**6):
    if dp[N][i] <= W: 
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import os, sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")
 
sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10**18
MOD = 10**9 + 7

def N(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))
def bulk_li(): return list(map(lambda s: list(map(int, s.split())), sys.stdin.readlines()))

n, w = li()
wv = bulk_li()

# print(wv)
table = dict()

# 以下の条件で最大の価値の総和を返す
# i番目以降(i+1..n)の品物 / 残重量jのナップサック
def dp(i, j):
    if i == n:
        return 0
    if (i, j) in table:
        return table.get((i, j))

    w, v = wv[i]
    if w > j:
        return dp(i+1, j)

    table[(i, j)] = max(v + dp(i+1, j-w), dp(i+1, j))
    return table[(i, j)]

print(dp(0, w))


"""
"""

Submission status: Time Limit Exceeded

Solution code:
# temp
n,w = map(int,input().split())
wv = [tuple(map(int,input().split())) for i in range(n)]

dp = [0] + [float("inf")]*(10**5)
for i in range(n):
    for j in range(10**5,wv[i][1]-1,-1):
        dp[j] = min(dp[j],dp[j-wv[i][1]]+wv[i][0])

res = 0
for v,e in enumerate(dp):
    if e <= w:
        res = v
print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, w = [int(e) for e in input().split()]
  d = [[int(e) for e in input().split()] for i in range(n)]
  t = {}
  t[w] = 0
  for i in range(n):
    keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
    tw, tv = d[i]
    for j in keys:
      nw = j - tw
      if nw < 0:
        continue
      nv = t[j] + tv
      if nw in t:
        if nv > t[nw]:
          t[nw] = nv
      else:
        t[nw] = nv
  print(max(t.values()))
main()

Submission status: Time Limit Exceeded

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

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


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

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

Submission status: Time Limit Exceeded

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

max_v = 100005

dp = [[float('inf') for i in range(max_v)] for j in range(n + 1)]

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

ans = 0
for sum_v in reversed(range(max_v)):
    if dp[-1][sum_v] <= w:
        print(sum_v)
        break

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

sv = {}
for ww, vv in a:
    added = {}
    for k, v in sv.items():
        added[ww+k] = vv+v
    for k, v in added.items():
        if (k <= w) and (k not in sv or v > sv[k]):
            sv[k] = v

    if (ww <= w) and (ww not in sv or vv > sv[ww]):
        sv[ww] = vv

print(max(sv.values()))

Submission status: Time Limit Exceeded

Solution code:
memo = {}

def check(x, y):
    val = True
    try:
        dummy = memo[f(x,y)]
    except KeyError:
        val = False
    else:
        dummy = 13
    return val;

def f(x, y):
    return ((x+y)*(x+y+1))//2 + y;

def knap(N, W):
    if 1 - check(N,W):
        if N == 0 or W == 0:
            memo[f(N,W)] = 0
        elif weight[N] > W:
            memo[f(N,W)] = knap(N-1, W)
        else:
            memo[f(N,W)] = max(knap(N-1, W), value[N] + knap(N-1, W - weight[N]))
        return memo[f(N,W)];
    else:
        return memo[f(N,W)];

N, W = [int(x) for x in input().split()]
weight = [0]
value = [0]

for _ in range(N):
    w, v = [int(x) for x in input().split()]
    weight.append(w)
    value.append(v)

print(knap(N,W))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
mx = 100000
dp = [[k+1 for _ in range(mx+1)]for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
    dp[i][0]= 0
    w,v = map(int,input().split())
    for j in range(v):
        dp[i][j]= dp[i-1][j]
    for j in range(v,mx+1):
        next = w+dp[i-1][j-v]
        if next<=k:
            dp[i][j]= min(next,dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(mx,-1,-1):
    if dp[n][i]<=k:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
n,k= map(int,input().split())
mxScore = set()
items= []
for i in range(n):
    w,v = map(int,input().split())
    items.append([w,v])
def factory(item,weight,value):
    if item==n or weight==k:
        mxScore.add(value)
    else:
        w, v = items[item]
        factory(item + 1,weight, value)
        if weight+w<=k:
            factory(item+1,weight+w,value+v)
factory(0,0,0)
print(max(mxScore))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
n,k= map(int,input().split())
mxScore = set()
items= []
for i in range(n):
    w,v = map(int,input().split())
    items.append([w,v])
def factory(item,weight,value):
    if item==n:
        mxScore.add(value)
    else:
        w, v = items[item]
        factory(item + 1,weight, value)
        if weight+w<=k:
            factory(item+1,weight+w,value+v)
factory(0,0,0)
print(max(mxScore))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def doit(i, w):
    if i < 0:
        return 0
    if (i, w) in memo:
        return memo[(i, w)]
    weight, val = weights[i], vals[i]
    memo[(i, w)] = max(val + doit(i - 1, w - weight) if weight <= w else 0, doit(i - 1, w))
    return memo[i, w]

memo = {}
print(doit(n - 1, weight))

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
u,m=[list(map(int,input().split()))for _ in range(n)],0
for i in u:m+=i[1]
dp=[[0]+[10000001]*m]+[[0]*(m+1)for _ in range(n)]
h=0
for i in range(1,n+1):
  a,b=map(int,u[i-1])
  for j in range(1,m+1):
    if j>=b:dp[i][j]=min(dp[i-1][j],dp[i-1][j-b]+a)
    else:dp[i][j]=dp[i-1][j]
a=0
for i in range(m+1):
  if dp[-1][i]<=w:a=max(a,i)
print(a)

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
val=[]
we=[]
for i in range(n):
  a,b=map(int,input().split())
  we.append(a)
  val.append(b)
dp=[[0 for _ in range(w+1)]for _ in range(2)]
i=0
while(i<n):
  j=0
  if i%2==0:
    while j<w:
      j+=1
      if we[i]>j:
        dp[1][j]=dp[0][j]
      else:
        dp[1][j]=max(dp[0][j],val[i]+dp[0][j-we[i]])
      
  if i%2==1:
      
      while j<w:
        j+=1
        if we[i]>j:
          dp[0][j]=dp[1][j]
        else:
          dp[0][j]=max(dp[1][j],val[i]+dp[1][j-we[i]])
      
  i+=1
if n%2==0:
    print(dp[0][w])
else:
    print(dp[1][w])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
val=[]
we=[]
for i in range(n):
  a,b=map(int,input().split())
  we.append(a)
  val.append(b)
dp=[[0 for _ in range(w+1)]for _ in range(n+1)]
for i in range(n+1):
  for j in range(w+1):
    if i==0 or j==0:
      continue
    if we[i-1]>j:
      dp[i][j]=dp[i-1][j]
    else:
      dp[i][j]=max(dp[i-1][j],val[i-1]+dp[i-1][j-we[i-1]])
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
dp = {0: 0}
ans = 0
for wi, vi in ((map(int, input().split())) for _ in range(n)):
    newvals = {}
    for k in dp.keys():
        if k + wi <= w:
            old_value = 0 if dp.get(k + wi) is None else dp.get(k + wi)
            newvals[k + wi] = max(dp.get(k) + vi, old_value, vi)
            ans = max(ans, newvals[k + wi])
    dp.update(newvals)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
dp = {0: 0}
ans = 0
for wi, vi in ((map(int, input().split())) for _ in range(n)):
    newvals = {}
    for k in sorted(dp.keys()):
        if k + wi <= w:
            old_value = 0 if dp.get(k + wi) is None else dp.get(k + wi)
            newvals[k + wi] = max(dp.get(k) + vi, old_value, vi)
            ans = max(ans, newvals[k + wi])
    dp.update(newvals)
print(ans)

Submission status: Time Limit Exceeded

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

DP = dict()
DP[W] = 0

def maxv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v > DP[i]:
            DP[i] = v

for w, v in (map(int, input().split()) for _ in range(N)):
    DPpre = DP.copy()
    for i in DPpre:
        if i - w >= 0:
            maxv(i-w, DPpre[i]+v)

print(max((DP[x] for x in DP)))

Submission status: Time Limit Exceeded

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

DP = dict()
DP[W] = 0
DPpre = dict()

def maxv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v > DP[i]:
            DP[i] = v
ls = list(list(map(int, input().split())) for _ in range(N))

for w, v in sorted(ls, reverse=True):
    DPpre, DP = DP, DPpre
    for i in DPpre:
        maxv(i, DPpre[i])
        if i - w >= 0:
            maxv(i-w, DPpre[i]+v)

print(max((DP[x] for x in DP)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

DP = dict()
DP[W] = 0
DPpre = dict()

def maxv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v > DP[i]:
            DP[i] = v

for w, v in (map(int, input().split()) for _ in range(N)):
    DPpre, DP = DP, DPpre
    for i in DPpre:
        maxv(i, DPpre[i])
        if i - w >= 0:
            maxv(i-w, DPpre[i]+v)

print(max((DP[x] for x in DP)))

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[float('inf')]*(N*1000+1)for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    w,v = wv[i]
    for j in range(N*1000+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)
for i in range(len(DP[-1])-1,-1,-1):
    if DP[-1][i] <= W:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as d
s=d(int)
s[0]=0
n,w=map(int,input().split())
for i in range(n):
    q,v=map(int,input().split())
    c=s.copy()
    for p,r in c.items():
        if p+q<=w:
            s[p+q]=max(s[p+q],r+v)
print(max(s.values()))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def main():
    num, max_weigh = map(int, input().split())
    now_dp = defaultdict(int)
    next_dp = defaultdict(int)
    now_dp[0] = 0

    for i in range(num):
        weight, value = map(int, input().split())
        for now_weigh in list(now_dp.keys()):
            next_dp[now_weigh] = max(now_dp[now_weigh], next_dp[now_weigh])
            if now_weigh + weight <= max_weigh:
                next_dp[now_weigh + weight] = max(now_dp[now_weigh] + value, now_dp[now_weigh + weight])
        now_dp = next_dp
        next_dp = defaultdict(int)
    print(max(list(now_dp.values())))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#dp5 #Knapsack 2
#個数制限ありナップサック
#1≤W≤10**9
import sys
def LI(): return list(map(int, sys.stdin.readline().split()))
def LIR(n): return [LI() for _ in range(n)]
def e():
    n,W = LI()
    wv = LIR(n)

    #横:価値　縦:品物
    dp = [[float("inf") for _ in range(10**5+1)] for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(1,n+1):
        for j in range(10**5+1):
            #i番目の品物の価値より価値の制限が小さいとき(i番目の品物が使えないとき)
            if j < wv[i-1][1]:
                #i-1番目の品物の重さと同じ
                dp[i][j] = dp[i-1][j]
            else:
                #i番目の品物を使い、重さを追加する場合と使わない場合の重さを比較
                dp[i][j] = min(dp[i-1][j],dp[i-1][j - wv[i-1][1]] + wv[i-1][0])
    ans = 0
    #重さWまでの価値最大値
    for i in range(10**5+1):
        if dp[n][i] <= W:
            ans = i
    print(ans)
if __name__ == '__main__':
    e()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#dp5 #Knapsack 2
#個数制限ありナップサック
#1≤W≤10**9

def e():
    n,W = map(int,input().split())
    wv = [list(map(int,input().split())) for _ in range(n)]
    #横:価値　縦:品物
    dp = [[float("inf") for _ in range(10**5+1)] for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(1,n+1):
        for j in range(10**5+1):
            #i番目の品物の価値より価値の制限が小さいとき(i番目の品物が使えないとき)
            if j < wv[i-1][1]:
                #i-1番目の品物の重さと同じ
                dp[i][j] = dp[i-1][j]
            else:
                #i番目の品物を使い、重さを追加する場合と使わない場合の重さを比較
                dp[i][j] = min(dp[i-1][j],dp[i-1][j - wv[i-1][1]] + wv[i-1][0])
    ans = 0
    #重さWまでの価値最大値
    for i in range(10**5+1):
        if dp[n][i] <= W:
            ans = i
    print(ans)
if __name__ == '__main__':
    e()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
def factorial(n):
    if (n==0) or (n==1):
        return 1
    ret = 1
    for i in range(2, n+1):
        ret *= i
    return ret
def combination(n, k):
    return factorial(n)//factorial(k)//factorial(n-k)
sys.setrecursionlimit(1000000)
INF = float("inf")
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, W = LI()
wv = LIR(N)
V = sum(list(map(lambda x: x[1], wv)))

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

for i in range(N):
    w, v = wv[i]
    for j in range(V+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)

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

Submission status: Time Limit Exceeded

Solution code:

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

wv = []
vmax = 0

for i in range(N):

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

    vmax += v
    wv.append([w,v])


lis = [[0] + [float("inf")] * vmax]

for i in wv:

    new = [0] + [float("inf")] * vmax

    for j in range(vmax+1):

        new[j] = min(new[j] , lis[-1][j])

        if j + i[1] <= vmax:

            new[j + i[1]] = min (new[j + i[1]] , lis[-1][j] + i[0])

    lis.append(new)

#print (lis)

lis[-1].reverse()

for i in range(vmax+1):

    if lis[-1][i] <= W:
        print (vmax - i)
        break

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
INF = float('inf')
weight = [0] * N
value = [0] * N
Max_v = 0
for i in range(N):
    w, v = map(int, input().split())
    weight[i], value[i] = w, v
    Max_v += v

dp = [[INF]*(Max_v+1) for _ in range(N)]
for i in range(0, value[0]+1):
    dp[0][i] = weight[0] if i else 0

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

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

Submission status: Time Limit Exceeded

Solution code:
n, weightMax = map(int, input().split())
itemList = [[0 for _ in range(weightMax+1)] for _ in range(n+1)]

for i in range(n):
    w,v = list(map(int, input().split()))
    for j in reversed(range(weightMax+1)):
        if j-w >= 0:
            itemList[i+1][j] = max([itemList[i][j],itemList[i][j-w] + v])
        else:
            itemList[i+1][j] = itemList[i][j]
print(max(itemList[n]))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for x in range(N)]
ws = [x[0] for x in wv]
vs = [x[1] for x in wv]

# depthまでの荷物で、value以上になる重さの最小
dp = [[None] * (sum(vs) + 1) for _ in range(N)]
def dfs(value=0, depth=N - 1):
    if value <= 0:
        return 0

    if depth == -1:
        return float("inf")

    if dp[depth][value] is not None:
        return dp[depth][value]

    weight = min(dfs(value, depth - 1), dfs(value - vs[depth], depth - 1) + ws[depth])
    dp[depth][value] = weight
    return weight

for i in range(sum(vs) + 1):
    if dfs(i) > W:
        print(i - 1)
        break
else:
    print(i)

Submission status: Time Limit Exceeded

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

dp = [[float('inf')] * (V+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で価値がj以上になるように選んだときの重さの最小値
dp[0][0] = 0
for i in range(N):
  for j in range(V+1):
    if v[i] <= j:# 荷物v[i]の価値がjに足りてないのでi番目の荷物を入れる可能性がある
      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])

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

Submission status: Time Limit Exceeded

Solution code:
# D-Knapsack 1
N,W = map(int,input().split())
Weight = [0 for _ in range(N)]
Value = [0 for _ in range(N)]
for i in range(N):
    Weight[i],Value[i] = map(int,input().split())

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

for i in range(N):
    # あらゆる合計重量sum_wに対して品物iを入れるべきか計算する
    for sum_w in range(W+1):
        # i番目を選ぶ場合
        if sum_w - Weight[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - Weight[i]] + Value[i])

        #　i番目を選ばない場合
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

# for d in dp:
#     print(d)

print(dp[N][W])

Submission status: Time Limit Exceeded

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

for i in range(N):
    a,b=map(int,input().split())
    arr[i]=a
    value[i]=b


def coin(arr,value,W,n):
    if n<0 or W==0:
        return 0

    elif arr[n]>W:
#        print(1)
        return coin(arr,value,W,n-1)
    elif n==0 and W>0:
#        print(2)
        return coin(arr,value,W-arr[n],n-1)+value[n] 
    else:
#        print(W)
        return max(coin(arr,value,W-arr[n],n-1)+value[n],coin(arr,value,W,n-1))


print(coin(arr,value,W,N-1))

Submission status: Time Limit Exceeded

Solution code:
import sys

n, w = [int(x) for x in input().split(" ")]

wv_list = []

for i in range(n):
  wv_list.append([int(x) for x in input().split(" ")])

dp = [[0 for y in range(w+2)] for x in range(n+1)]

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

Submission status: Time Limit Exceeded

Solution code:
n, W = map(int, input().split(' '))
ws = [0] * (n+1)
vs = [0] * (n+1)
for i in range(1, n+1):
	ws[i], vs[i] = map(int, input().split(' '))

# dp[合計価値] = 合計重さ
sumVs = sum(vs)
dp = [W+1] * (sumVs + 1)	# 存在しない価値には重さのペナルティをつける
dp[0] = 0

# 品物で回す
for w, v in zip(ws, vs):
	# 価値で回す
	for i in range(sumVs, v-1, -1):
		dp[i] = min(dp[i], dp[i-v] + w)

# 制限荷重内の最大合計価値を求める
for i in range(sumVs, 0, -1):
	if(dp[i] <= W):
		print(i)
		break

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
    w1,v1=map(int,input().split())
    w[i]=w1
    v[i]=v1
dp=[[0 for i in range(W+1)] for j in range(N)]
for i in range(N):
    if i==0:
        dp[0][w[0]]=v[0]
    else:
        for w1 in range(W+1):
            if 0<=w1-w[i]:
                dp[i][w1]=max((dp[i-1][w1-w[i]]+v[i]),dp[i-1][w1])
            else:
                dp[i][w1]=dp[i-1][w1]
print(max(dp[N-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())
V=sum(v)
dp=[[float('inf')]*(V+1) for i in range(N+1)] #初期化はfor より *の方が早い

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

for j in range(V+1):
    if dp[N][j]<=W:
        res=j
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
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())
V=sum(v)
dp=[[float('inf') for i in range(V+1)] for j in range(N+1)]

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

for j in range(V+1):
    if dp[N][j]<=W:
        res=j
print(res)

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())
V=sum(v)
dp=[[float('inf') for i in range(V+1)] for j in range(N+1)]

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

for j in range(V+1):
    if dp[N][j]<=W:
        res=j
print(res)

Submission status: Time Limit Exceeded

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

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())
V = sum(v)
dp = [[float("inf")] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
	for j in range(V + 1):
		if j - v[i] >= 0:
			dp[i + 1][j] = dp[i][j - v[i]] + w[i]
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
ans = 0
for j in range(V + 1):
	if dp[N][j] <= W:
		ans = j
print(ans)

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())

V = sum(v)
dp = [[float("inf")] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
	for j in range(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])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,W=map(int, input().split())
a=[]
max_v=0
for _ in range(n):
    w,v=map(int, input().split())
    a.append((w,v))
    max_v+=v

dp=[[float('inf') for j in range(max_v+1)] for i in range(n+1)] # dp[n][v] = min weight using up to n-th items and value = v

for i in range(1,n+1):
    w,v=a.pop()
    for j in range(max_v+1):
        if j-v>=0:
            dp[i][j]=min(
                dp[i-1][j-v]+w # use j-th item (w,v)
                ,dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
    dp[i][v]=min(w,dp[i-1][v])
    
ans=0
for j in range(max_v+1):
    if dp[n][j]<=W:
        ans=j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


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

    for i, (cw, cv) in enumerate(zip(w, v)):
        for j in range(N * 1000 + 1):
            dp[i+1][j] = dp[i][j]
            if 0 <= (j - cv) and (dp[i][j - cv] + cw) <= W:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j - cv] +  cw)

    return max([cv for cv, cw in enumerate(dp[-1]) if isfinite(cw)])


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))
    result = solve(N, W, w, v)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
v_max = sum([i[1] for i in items])
INF = 10**12
dp = np.array([[INF for j in range(N * v_max+1)] for _ in range(N+1)])
dp[0, 0] = 0
for i in range(1, N+1):
    w, v = items[i-1]
    dp[i, :v] = dp[i-1, :v]
    dp[i, v:] = np.minimum(dp[i-1, :-v] + w, dp[i-1, v:])
ans = 0
for v in range(N * v_max, -1, -1):
    if dp[N][v] <= W:
        ans = v
        break
print(ans)

Submission status: Time Limit Exceeded

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

INF = 10 ** 12
V = 10 ** 3 * 100 + 10

dp = [0] + [INF] * V
for w, v in WV:
	for i in range(V, v - 1, -1):
		dp[i] = min(dp[i], dp[i - v] + w)

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

"""
for cell in dp:
	if cell == INF:
		print("  INF", end="")
	else:
		print("{:5d}".format(cell), end="")
print()
"""

Submission status: Time Limit Exceeded

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

import math
INF = 10 ** 18 # math.inf
V = 10 ** 5 + 10

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

for i, (w, v) in enumerate(WV):
	for n in range(V):
		if v <= n:
			dp[i + 1][n] = min(dp[i + 1][n], dp[i][n - v] + w)
		dp[i + 1][n] = min(dp[i + 1][n], dp[i][n])
"""
for line in dp:
	for cell in line:
		if cell == INF:
			print("  INF", end="")
		else:
			print("{:5d}".format(cell), end="")
	print()
"""
r = 0
for i in range(V):
	if dp[-1][i] <= W:
		r = i
print(r)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n, max_w = map(int, input().split())

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

for i in range(n):
    w, v = map(int, input().split())
    queue = list()
    for i in range(max_w, w - 1, -1):
        dp[i] = max(dp[i], dp[i - w] + v)

print(max(dp))