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=list(map(int,input().split()))
k=[]
for i in range(n):
    k.append(list(map(int,input().split())))
vn=max([k[i][1] for i in range(n)])*n
dp=[[0]+[float("inf") for i in range(vn)] for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,vn+1):
        if j<=k[i-1][1]:
            dp[i][j]=min(dp[i-1][j],k[i-1][0])
        else:
            dp[i][j]=min(dp[i-1][j],k[i-1][0]+dp[i-1][j-k[i-1][1]])
for i in range(vn,-1,-1):
    if dp[n][i]<=w:
        print(i)
        break

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
weighs,values = [],[]
for i in range(n):
    wa,va = map(int,input().split())
    weighs.append(wa)
    values.append(va)

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

for i in range(w+1):
    maxa = 0
    useda = [0 for i in range(n)]
    for k in range(n):
        if used[i-weighs[k]][k] == 0 and i-weighs[k] >= 0 and dp[i-weighs[k]]+values[k]>maxa:
                maxa = dp[i-weighs[k]]+values[k]
                useda = used[i-weighs[k]][:]
                useda[k] = 1
    dp[i] = maxa
    used[i] = useda

#print(used)
print(max(dp))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N , W = map(int, input().split() )
wv = [list(map(int,input().split())) for _ in range(N) ]
maxv = 100100
dp = [[10**10] * (maxv) for _ in range(N+1) ]
dp[0][0] = 0
for i in range(N):
    for j in range(maxv):
        if j >= wv[i][1]:
            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 j in range(maxv):
    if dp[N][j] <= W:
        ans = j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys

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

dp = [float('inf')] * (10**5+1)
dp[0] = 0

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

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

Submission status: Time Limit Exceeded

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

INF = float("inf")
MAX_V = 100 * 10 ** 3

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

dp = [[INF for _ in range(MAX_V)] for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
	for j in range(MAX_V):
		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])

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
w = []
v = []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
VM = sum(v) + 10
dp = [[float('inf') for _ in range(VM)] for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(VM):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        if j - v[i] >= 0:
            if dp[i][j - v[i]] + w[i] <= W:
                dp[i + 1][j] = min(dp[i][j - v[i]] + w[i], dp[i + 1][j])
ans = 0
for i in range(VM):
    if dp[N][i] < float('inf'):
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
items = [tuple(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(N):
    for j in range(10 ** 5 + 1):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        if j - items[i][1] >= 0:
            if dp[i][j - items[i][1]] + items[i][0] <= W:
                dp[i + 1][j] = min(dp[i][j - items[i][1]] + items[i][0], dp[i + 1][j])
ans = 0
for i in range(10 ** 5 + 1):
    if dp[N][i] < float('inf'):
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python2
"""
This file is part of https://github.com/cheran-senthil/PyRival
Copyright 2019 Cheran Senthilkumar <hello@cheran.io>

"""
from __future__ import division, print_function

import itertools
import os
import sys
from atexit import register
from io import BytesIO


class dict(dict):
    """dict() -> new empty dictionary"""

    def items(self):
        """D.items() -> a set-like object providing a view on D's items"""
        return dict.iteritems(self)

    def keys(self):
        """D.keys() -> a set-like object providing a view on D's keys"""
        return dict.iterkeys(self)

    def values(self):
        """D.values() -> an object providing a view on D's values"""
        return dict.itervalues(self)


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


range = xrange

filter = itertools.ifilter
map = itertools.imap
zip = itertools.izip

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

input = lambda: sys.stdin.readline().rstrip('\r\n')


def memoize(f):
    """ Memoization decorator for a function taking one or more arguments. """

    class memodict(dict):
        def __getitem__(self, *key):
            return dict.__getitem__(self, key)

        def __missing__(self, key):
            ret = self[key] = f(*key)
            return ret

    return memodict().__getitem__


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

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


@memoize
def solve(x, y):
    if x == n:
        return 0
    if y < w[x]:
        return solve(x + 1, y)
    return max(v[x] + solve(x + 1, y - w[x]), solve(x + 1, y))


print(solve(0, m))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n, w =  [int(x) for x in stdin.readline().rstrip().split()]
item = []
for i in range(n):
    item.append([int(x) for x in stdin.readline().rstrip().split()])
maxv = 0
for i in range(n):
    maxv += item[i][1]
dp = [[float('inf')] * (maxv + 1) for i in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
    for v in range(maxv + 1):
        nv = v - item[i - 1][1]
        if nv >= 0:
            ndp = dp[i - 1][nv] + item[i - 1][0]
            if dp[i][v] > ndp:
                dp[i][v] = ndp
        if dp[i][v] > dp[i-1][v]:
            dp[i][v] = dp[i-1][v]
ans = [i for i, x in enumerate(dp[n]) if x <= w]
print(max(ans))

Submission status: Time Limit Exceeded

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:

n, w = map(int, raw_input().split())
oo = w + 1
items = []
v = 0
for _ in range(n):
    wi, vi = map(int, raw_input().split())
    items.append((wi, vi))
    v += vi

dp = [[oo] * (v + 1) for _ in range(n + 1)]
for i in xrange(n + 1):
    dp[i][0] = 0
for i in xrange(1, n + 1):
    wi, vi = items[i - 1]

    for j in range(1, vi):
        dp[i][j] = dp[i - 1][j]

    for j in range(vi, v + 1):
        if j >= vi:
            dp[i][j] = min(dp[i - 1][j], wi + dp[i - 1][j - vi])
for i in xrange(v, -1, -1):
    if dp[n][i] <= w:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:

n, w = map(int, raw_input().split())
oo = w + 1
items = []
v = 0
for _ in range(n):
    wi, vi = map(int, raw_input().split())
    items.append((wi, vi))
    v += vi

dp = [[oo] * (v + 1) for _ in range(n + 1)]
for i in xrange(n + 1):
    dp[i][0] = 0
for i in xrange(1, n + 1):
    wi, vi = items[i - 1]
    for j in range(1, v + 1):
        dp[i][j] = dp[i - 1][j]
        if j >= vi:
            dp[i][j] = min(dp[i][j], wi + dp[i - 1][j - vi])
for i in xrange(v, -1, -1):
    if dp[n][i] <= w:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:


n, w = map(int, raw_input().split())
oo = w + 1
items = []
v = 0
for _ in range(n):
    wi, vi = map(int, raw_input().split())
    items.append((wi, vi))
    v += vi

dp = [[oo] * (v + 1) for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 0
for i in range(1, n + 1):
    wi, vi = items[i - 1]
    for j in range(1, v + 1):
        dp[i][j] = dp[i - 1][j]
        if j >= vi:
            dp[i][j] = min(dp[i][j], wi + dp[i - 1][j - vi])
for i in range(v, -1, -1):
    if dp[n][i] <= w:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
L = 1000000
dp = [[10000000010 for _ in range(L+1)] for _ in range(N+1)]
W, V = [], []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
dp[0][0] = 0
for i in range(N):
    for j in range(L):
        if j + V[i] <= L:
            dp[i+1][j] = min(dp[i][j], dp[i][j-V[i]] + W[i])
        else:
            dp[i+1][j] = dp[i][j]
for i, d in enumerate(dp[N]):
    if d <= M:
        maxv = i
print(maxv)

Submission status: Time Limit Exceeded

Solution code:
n,k=(int(i) for i in input().split())

e = [[int(i) for i in input().split()] for j in range(n)]
#print(e)

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

for j in range(k+1):
    if j >= e[0][0]:
      dp[0][j]=e[0][1]

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

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

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
w=[]
v=[]
MAX_N = 110
MAX_V=100100
dp =[[float("inf") for i in range(MAX_V)] for j in range(MAX_N)]
dp[0][0] = 0

for i in range(n):
    a,b = map(int,input().split())
    w.append(a)
    v.append(b)
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][sum_v],dp[i][sum_v - v[i]] + w[i])
        
        dp[i+1][sum_v]=min(dp[i][sum_v],dp[i+1][sum_v])
for sum_v in range(MAX_V):
    if dp[n][sum_v] <= k:
        res = sum_v
print(res)

Submission status: Time Limit Exceeded

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

upper = 10**5
dp = [float("inf") for i in range(upper+1)]
dp[0] = 0

for item in range(N) :
    weight_i,value_i = L[item]
    for value in range(upper, value_i-1, -1) :
        if dp[value - value_i] + weight_i <= W :
            dp[value] = min(dp[value], dp[value - value_i] + weight_i)

for value in range(upper, -1, -1) :
    if dp[value] < float("inf") :
        ans = value
        break

print(ans)

Submission status: Time Limit Exceeded

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

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


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

Submission status: Time Limit Exceeded

Solution code:
def main():
  N, W = list(map(int, input().split()))
  Data = []
  su = 0
  for i in range(N):
    t = list(map(int, input().split()))
    su += t[1]
    Data.append(t)
  
  DP = [int(10e12) if i != Data[0][1] else Data[0][0] for i in range(su + 1)]
  DP[0] = 0
  
  for i in range(1, N):
    for j in range(su - Data[i][1], -1, -1):
      k = j + Data[i][1]
      DP[k] = min(DP[j] + Data[i][0], DP[k])
      
  for i in range(su, -1, -1):
    if DP[i] <= W:
      print(i)
      break
  
main()

Submission status: Time Limit Exceeded

Solution code:
import itertools as itr

n, wmax = list(map(int, input().split()))
w = [0]*(n+1)
v = [0]*(n+1)

for i in range(1, n+1):
    wi, vi = list(map(int, input().split()))
    w[i] = wi
    v[i] = vi
vmax = sum(v)
    
dp = [[10**9+7]*(vmax+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0]=0

for i, j in itr.product(range(1, n+1), range(1, vmax+1)):
    if j-v[i] >= 0:
        dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]]+w[i])
        #print((i,j), dp[i][j])
    else:
        dp[i][j] = dp[i-1][j]

ans = [j for j in range(vmax+1) if dp[n][j] <= wmax]       
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
N, W = map( int, input().split())
dp = [10**9+1]*(10**5+2)
dp[0] = 0
for _ in range(N):
    w, v = map( int, input().split())
    #iを実現しうる最小のwを更新すればよいのでは
    for i in range(10**5,0,-1):
        if i <= v:
            dp[i] = min( dp[i], w)
        else:
            if dp[i-v] + w <= W:
                dp[i] = min( dp[i-v] + w, dp[i])
print( dp.index(10**9+1)-1)

Submission status: Time Limit Exceeded

Solution code:
import functools
N, W = map(int, input().split())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])
maxV = max(vs)
V = maxV * N
INF = 10**10

dp = {}
def minweight(i, v):
    if (i, v) not in dp:
        if i == 0:
            if v == 0: dp[i, v] = 0
            elif v == vs[i]: dp[i, v] = ws[i]
            else: dp[i, v] = INF
        else:
            if vs[i] <= v:
                dp[i, v] = min(minweight(i - 1, v - vs[i]) + ws[i], minweight(i - 1, v))
            else:
                dp[i, v] = minweight(i - 1, v)
    return dp[i, v]

for v in range(V, -1, -1):
    if minweight(N - 1, v) <= W:
        print(v)
        break

Submission status: Time Limit Exceeded

Solution code:
import functools
N, W = map(int, input().split())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])

@functools.lru_cache(None)
def maxvalue(i, w):
    if i < 0: return 0
    if w < ws[i]:
        return maxvalue(i - 1, w)
    else:
        return max(maxvalue(i - 1, w), maxvalue(i - 1, w - ws[i]) + vs[i])

print(maxvalue(N - 1, W))

Submission status: Time Limit Exceeded

Solution code:
N, W = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(N)]
dp = {}
dp[0] = 0
for w, v in WV:
    dp_o = dp.copy()
    for k in dp_o:
        dp[k + v] = min(dp_o.get(k + v, float('inf')), dp_o[k] + w)
print(max([k for k, v in dp.items() if v <= W]))

Submission status: Time Limit Exceeded

Solution code:
N, W = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(N)]
dp = {}
dp[0] = 0
for w, v in WV:
    dp_o = dp.copy()
    for k in dp_o:
        if k + w <= W:
            dp[k + w] = max(dp_o.get(k + w, 0), dp_o[k] + v)
print(max([v for k, v in dp.items()]))

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_e
#2019-01-13
import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]

DP = np.ones(N*1000+1,dtype = int) *(W+1)
DP[0] = 0
#総価値 i 円を得るために最低限必要な重量
for i in range(N):
    for j in range(N*1000,-1,-1):
        DP[j] = min(DP[j- v[i]] + w[i], DP[j])
ans = 0
for k in range(N*1000+1):
    if DP[k] <= W:
        
        ans = k
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
X = [0] + [-1] * 110000
ma = 0
for i in range(N):
    w, v = map(int, input().split())
    
    for j in range(len(X))[::-1]:
        if X[j] >= 0:
            if X[j] + w <= W:
                if X[j+v] < 0:
                    X[j+v] = X[j]+w
                    ma = max(ma, j+v)
                else:
                    X[j+v] = min(X[j+v], X[j]+w)

print(ma)

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: 0}
for i in range(N):
    for cv, cw in list(dp.items()):
        if cw + w[i] > W:
            continue
        dp[cv + v[i]] = min(
            dp.get(cv + v[i], float('inf')),
            cw + w[i])
print(max(dp))

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: 0}
for i in range(N):
    for cw, cv in list(dp.items()):
        if cw + w[i] > W:
            continue
        dp[cw + w[i]] = max(
            dp.get(cw + w[i], 0),
            cv + v[i])
print(max(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
INF = int(2e9)
n, W = map(int, input().split())
dp = [INF] * int(1e6)
dp[0] = 0
for i in range(n):
    w, v = map(int, readline().split())
    for j in range(int(1e5) - 1, -1, -1):
        if dp[j] + w <= W:
            dp[j + v] = min(dp[j + v], dp[j] + w)
for i in range(int(1e5), -1, -1):
    if dp[i] != INF:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
INF = int(2e9)
n, W = map(int, input().split())
dp = [INF] * int(1e6)
dp[0] = 0
for i in range(n):
    w, v = map(int, input().split())
    for j in range(int(1e5) - 1, -1, -1):
        if dp[j] + w <= W:
            dp[j + v] = min(dp[j + v], dp[j] + w)
for i in range(int(1e5), -1, -1):
    if dp[i] != INF:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
w_v = [list(map(int, input().split())) for _ in range(N)]
 
 
# 1~i-1番目の品物から重さの総和がj以下になるように選んだときの価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
 
for i in range(N):
    w, v = w_v[i]
    for j in range(W+1):
        if j - w >= 0:
            dp[i+1][j] = max(dp[i][j-w]+v, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
 
print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N,W = map(int, input().split())
wl = []
vl = []
for _ in range(N):
    w,v = map(int, input().split())
    wl.append(w)
    vl.append(v)

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

for vi in range(V+1):
    for i in range(N):
        if vi>=vl[i]:
            dp[i+1][vi] = min(
                dp[i][vi],
                dp[i][vi-vl[i]]+wl[i]
            )
        else:
            dp[i+1][vi] = dp[i][vi]

res = 0
for vi in range(V+1):
    if dp[N][vi]<=W:
        res = max(res, vi)

print(res)

Submission status: Time Limit Exceeded

Solution code:
n,wgt=map(int,input().split())
a=[]
v=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    v.append(y)

dp=[[0 for x in range(wgt+1)] for x in range(n+1)]

for i in range(n+1):
    for j in range(wgt+1):
        if i==0 or j==0:
            dp[i][j]=0
        elif a[i-1]<=j:
            dp[i][j]=max(v[i-1]+dp[i-1][j-a[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]

print(dp[n][wgt])

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())

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

for i in range(a):
	w,h = map(int,input().split())
	for j in range(b,w-1,-1):
		dp[j] = max(dp[j],dp[j-w] + h)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
goods = [list(map(int, input().split())) for i in range(N)]
v_sum = sum([i[1] for i in goods])
dp = [float("inf") for i in range(v_sum + 1)]
dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        dp[j] = min(dp[j - goods[i][1]] + goods[i][0], dp[j])

for i in range(v_sum, -1, -1):
    if dp[i] <= W:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
N, W = list(map(int, input().split()))
w = [-1 for i in range(N + 1)]
v = [-1 for i in range(N + 1)]
w[0] = 0;v[0] = 0;V = 0
for i in range(1, N+1):
    w[i], v[i] = list(map(int, input().split()))
    V += v[i]
INF = 1000000000
dp = [[INF for i in range(V + 1)] for j in range(N + 1)]
dp[0][0] = 0
# N <= 100 and V <= 10^3 O(N^2V) 10^7
reg = 0
for i in range(1, N + 1):
    for j in range(0, 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])
            if dp[i][j] <= W and j > reg:
                reg = j
print(reg)

Submission status: Time Limit Exceeded

Solution code:
V_TOTAL_MAX = 10 ** 5
INF = float('inf')

N, W = map(int, input().split())
dp = [[INF for _ in range(V_TOTAL_MAX + 1)] for _ in range(N + 1)]  # dp[品物番号][基準となる価値] = 重さの総和の最小値
dp[0][0] = 0

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, W = [int(i) for i in input().split()]
Things = [[int(i) for i in input().split()] for j in range(N)]

dp = defaultdict(int)
dp[0] = 0
for w, v in Things:
    for nw, nv in list(dp.items()):
        if nw + w <= W:
            dp[nw + w] = max(dp[nw + w], nv + v)
print(max(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
V = 10**5
INF = 10**18
dp = [INF]*(V+1)

dp[0] = 0
for i in range(N):
    w, v = map(int, input().split())
    for j in range(V, v-1, -1):
        if dp[j-v] + w <= W:
            dp[j] = min(dp[j], dp[j-v] + w)
for i in range(V, -1, -1):
    if dp[i] < INF:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
 
N,W = map(int, input().split())
WV = []
for i in range(N):
    WV.append(list(map(int, input().split())))
 
dp = defaultdict(int)
 
dp[0] = 0
 
for w,v in WV:
    for nw, nv in list(dp.items()):
        if nw+w <= W:
            dp[nw+w] = max(dp[nw+w], nv+v)
            
print(max(dp.values()))

Submission status: Accepted

Solution code:
INF=10**18
n,m=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
  w[i],v[i]=map(int,input().split())
k=sum(v)
dp=[INF]*(k+1)
dp[0]=0
for i in range(n):
  for j in range(k,-1,-1):
    if j>=v[i] and dp[j-v[i]]!=INF:dp[j]=min(dp[j],dp[j-v[i]]+w[i])
for i,x in enumerate(dp):
  if x<=m:ans=i
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w,v = [0 for _ in range(N)], [0 for _ in range(N)]
for i in range(N):
    w[i],v[i] = map(int,input().split())
SUM_V = sum(v)+1
# print(SUM_V)
INF = float('inf')
dp = [[INF for _ in range(SUM_V)] for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for sum_v in range(SUM_V):
        # print(i,sum_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][sum_v],dp[i+1][sum_v])
res = 0
# for i in dp:
#     print(i)

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

print(res)

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    weight = [0] * N
    value = [0] * N
    for i in range(N):
        weight[i], value[i] = map(int, input().split())
    V = sum(value)
    dp = [[float('inf')] * (V + 5) for _ in range(N + 5)]
    dp[0][0] = 0
    for i in range(N):
        for v in range(V+1):
            if v - value[i] >= 0:
                dp[i+1][v] = min(dp[i][v-value[i]] + weight[i], dp[i][v])
            else:
                dp[i+1][v] = dp[i][v]
    ans = 0
    for v in range(V+1):
        if dp[N][v] <= W:
            ans = v
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
num=[list(map(int,input().split())) for _ in range(n)]
cnt=0
for i in range(n):
    cnt+=num[i][1]
dp=[[10**10]*(cnt+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(1,n+1):
    w=num[i-1][0]
    v=num[i-1][1]
    for j in range(cnt+1):
        dp[i][j]=dp[i-1][j]
    dp[i][v]=min(dp[i][v],w)
    for j in range(1,cnt+1-v):
        if dp[i-1][j]!=10 and dp[i-1][j]+w<=p:
            dp[i][j+v]=min(dp[i][j+v],dp[i-1][j]+w)
ans=0
for i in range(n+1):
    for j in range(1,cnt+1):
        if dp[i][j]<=p:
            ans=max(ans,j)
print(ans)

Submission status: Accepted

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

#import
#import math
#import numpy as np
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

dp = [10 ** 10] * (10 ** 5 + 1)
dp[0] = 0

for w, v in wv:
    for i in range(10 ** 5, 0, -1):
        if i - v < 0:
            break

        dp[i] = min(dp[i], dp[i - v] + w)

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

Submission status: Accepted

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

def main():
    n, w = map(int, input().split())
    wv = [tuple(map(int, input().split())) for _ in range(n)]

    sum_v = sum([value for weight, value in wv])
    dp = [w + 1] * (sum_v + 1)
    dp[0] = 0
    for weight, value in wv:
        for i in range(sum_v - value + 1)[::-1]:
            if dp[i + value] > dp[i] + weight:
                dp[i + value] = dp[i] + weight

    for i in range(sum_v + 1)[::-1]:
        if dp[i] <= w:
            print(i)
            break

main()

Submission status: Accepted

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

MAX = 10**11 + 1
dp = [[MAX]*(N*10**3+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for j in range(0, N*10**3+1):
        if j == 0:
            dp[i][j] = 0
        elif j >= v_list[i-1]:
            dp[i][j] = min(dp[i-1][j], w_list[i-1]+dp[i-1][j-v_list[i-1]])
        else:
            dp[i][j] = dp[i-1][j]
    #print(dp[i]) 
ans = 10**6 + 1
for k in range(N*10**3+1):
    if dp[N][k] <= W:
        ans = k
#print(dp[N])
print(ans)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():


    n, w = LI()
    weight = [0 for _ in range(n+1)]
    value = [0 for _ in range(n+1)]

    for i in range(1,n+1):
        weight[i], value[i] = LI()


    dp = [[float("inf") for _ in range(sum(value)+1)]  for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(len(dp[0])):
            if j < value[i+1]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-value[i+1]] + weight[i+1])

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

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
l = [list(map(int,input().split())) for i in range(N)]
w,v = [list(i) for i in zip(*l)]
INF = 10**9+7
dp = [[INF] * (100001) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(100001):
        if j-v[i] >= 0:
            dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i])
        else:
            dp[i+1][j] = dp[i][j]
ans = 100000
while dp[N][ans] > W:
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
l = [list(map(int,input().split())) for i in range(N)]
w,v = [list(i) for i in zip(*l)]
INF = 10**9+7
dp = [[INF] * (100001) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    for j in range(100001):
        if j-v[i-1] >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1])
        else:
            dp[i][j] = dp[i-1][j]
ans = 100000
while dp[N][ans] > W:
    ans -= 1
print(ans)

Submission status: Accepted

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

MAXV = 10**5+1
INF = 10**18
dp = [[INF]*(MAXV+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    w, v = WV[i]
    for j in range(MAXV+1):
        dp[i+1][j] = dp[i][j]
    for j in range(MAXV+1):
        if j+v <= MAXV:
            dp[i+1][j+v] = min(dp[i][j]+w, dp[i+1][j+v])
ans = 0
for i in range(n+1):
    for j in range(MAXV+1):
        temp = dp[i][j]
        if temp <= W:
            ans = max(j, ans)
print(ans)

Submission status: Accepted

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

#制約から、品物と価値のdpにする
dp = [[float("inf")]*(sum(v)+1) for _ in range(n+1)]
dp[0][0] = 0
#dp[i][j]はi番目までの品物の中から、価値jを
for i in range(1, n+1):
    for j in range(sum(v) + 1):
        dp[i][j] = dp[i-1][j]
        if j - v[i] >= 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j-v[i]] + w[i])
ans = 0
for i in range(sum(v)+1):
    if dp[n][i] <= W:
        ans = max(ans, i)
#print(dp[n])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    import numpy as np

    N, W = map(int, input().split())
    lst = [list(map(int, input().split())) for _ in range(N)]
    v_max = 10 ** 3 * 100 * 10
    w_max = 10 ** 9 * v_max

    # i以上の価値を持つときの最小重量
    dp = np.full(v_max, w_max, dtype=np.int64)
    # initialize
    dp[0] = 0

    for w, v in lst:
        dp[v:] = np.minimum(dp[v:], dp[:-v] + w)

    print(np.asarray(dp <= W).nonzero()[0].max())


if __name__ == '__main__':
    main()