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())
w,v =[],[]

for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

max_v = 100100
max_n = 110
dp =[[float("inf")]*(max_v) for _ in range(max_n)]
dp[0][0] = 0
for i in range(N):
    for j in range(max_v):
        dp[i+1][j] = dp[i][j]
        if j - v[i] >= 0:
            dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]] + w[i])

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:
"""メモリ足りねぇ..."""

import sys
pin=sys.stdin.readline

INF=10**10
N,W=map(int,pin().split())

dp=[[INF]*100001 for _ in [0]*(N+1)]
dp[0][0]=0
for i in range(1,N+1):
  w,v=pin().split()
  w=int(w)
  v=int(v)
  for j in range(100001):
    if j-v>=0:
      dp[i][j]=min(dp[i-1][j],dp[i-1][j-v]+w)
    else:
      dp[i][j]=dp[i-1][j]
ans=100000
while dp[N][ans]>W:
  ans-=1
print(ans)
#解説AC

Submission status: Time Limit Exceeded

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

items = [list(map(int, input().split())) for i in range(n)]

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

dp[0][items[0][1]] = items[0][0]
dp[0][0] = 0

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

ans = 0
for i in range(len(dp[0])):
    if dp[-1][i] <= w:
        ans = i

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
knap = []
s_val = 0
for i in range(N):
    knap.append(tuple(map(int, input().split())))
    s_val += knap[i][1]
    
INF = 10**15
dp = [[INF for _ in range(s_val+1)] for _ in range(N+1)]  
dp[0][0] = 0

for i, (w, v) in enumerate(knap):
    for j in range(s_val+1):
        if(j >= v):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v]+w)
        
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

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

Submission status: Time Limit Exceeded

Solution code:
def edu_dp_e_knapsack2():
    n, c = map(int, input().split())
    w, v = [0], [0]
    for _ in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[float('inf')] * 100001 for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(1, n+1):
        for j in range(0, 100001):
            dp[i][j] = dp[i-1][j]
            if j >= v[i]:
                dp[i][j] = min(dp[i][j], dp[i-1][j-v[i]]+w[i])
    ans = 100000
    while dp[n][ans]>c:ans-=1
    print(ans)
edu_dp_e_knapsack2()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

#dp[i][j] = i番目までのお菓子の中から，ナップサックの中のお菓子の重さの総和がjを超えないようにいくつかお菓子を選んで詰めるとき，価値の最大値

for i in range(1, N+1):
    for j in range(1, W+1):
        if j - w[i] >= 0: #ex.ナップサックの耐加重がj=100,で, i番目のお菓子の重さが20である場合，ナップサックに追加することができるのは，i-1番目までのお菓子でまだ80以下の重さしかないとき。
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i])

        dp[i][j] = max(dp[i][j], dp[i-1][j])

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import math
N,W=map(int,input().split())
dp=[[math.inf for _ in range(100001)] for _ in range(N+1)]
#print(dp[-1][100000])
dp[0][0]=0
def min_(a,b):
  if a<b:
    return a
  else:
    return b
def nap():
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(100001):
      if j-v>=0:
        #print(dp[i-1][j-w[i]])
        dp[i+1][j]=min_(dp[i+1][j],dp[i][j-v]+w)
      dp[i+1][j]=min_(dp[i+1][j],dp[i][j])
  ans=100000
  #print(dp[0][:4])
  while dp[-1][ans]>W:
    ans-=1
  print(ans)

nap()

Submission status: Time Limit Exceeded

Solution code:
import math
N,W=map(int,input().split())
dp=[[math.inf for _ in range(100001)] for _ in range(N+1)]
#print(dp[-1][100000])
dp[0][0]=0

def nap():
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(100001):
      if j-v>=0:
        #print(dp[i-1][j-w[i]])
        dp[i+1][j]=min(dp[i+1][j],dp[i][j-v]+w)
      dp[i+1][j]=min(dp[i+1][j],dp[i][j])
  ans=100000
  #print(dp[0][:4])
  while dp[-1][ans]>W:
    ans-=1
  print(ans)

nap()

Submission status: Time Limit Exceeded

Solution code:
import math
N,W=map(int,input().split())
dp=[[math.inf for _ in range(100001)] for _ in range(N+1)]
#print(dp[-1][100000])
dp[0][0]=0
for i in range(N):
  w,v=map(int,input().split())
  for j in range(100001):
    if j-v>=0:
      #print(dp[i-1][j-w[i]])
      dp[i+1][j]=min(dp[i+1][j],dp[i][j-v]+w)
    dp[i+1][j]=min(dp[i+1][j],dp[i][j])
ans=100000
#print(dp[0][:4])
while dp[-1][ans]>W:
  ans-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,cap=map(int,input().split())
w=[]
v=[]
for _ in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
dp=[[0 for _ in range(cap+1)] for _ in range(n+1)]
for i in range(n+1):
    for c in range(cap+1):
        if c==0 or i==0:
            dp[i][c]=0
        elif c-w[i-1]>=0:
            dp[i][c]=max(dp[i-1][c],dp[i-1][c-w[i-1]]+v[i-1])
        else:
            dp[i][c]=dp[i-1][c]

print(dp[n][cap])

Submission status: Time Limit Exceeded

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

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

  
dp=[[float('inf')]*(sum(value)+1) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
  for j in range(sum(value)+1):
    dp[i+1][j]=min(dp[i+1][j],dp[i][j])
    dp[i+1][min(j+value[i],sum(value))]=min(dp[i+1][min(j+value[i],sum(value))],dp[i][j]+weight[i])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

  
dp=[[float('inf')]*(sum(value)+1) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
  for j in range(sum(value)+1):
    dp[i+1][j]=min(dp[i+1][j],dp[i][j])                             #+1、個数制限なし
    dp[i+1][np.minimum(j+value[i],sum(value))]=np.minimum(dp[i+1][np.minimum(j+value[i],sum(value))],dp[i][j]+weight[i])

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

print(ans)

Submission status: Time Limit Exceeded

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

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

  
dp=[[float('inf')]*(sum(value)+1) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
  for j in range(sum(value)+1):
    dp[i+1][j]=min(dp[i+1][j],dp[i][j])                             #+1、個数制限なし
    dp[i+1][min(j+value[i],sum(value))]=min(dp[i+1][min(j+value[i],sum(value))],dp[i][j]+weight[i])

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

print(ans)

Submission status: Time Limit Exceeded

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

dp=[[0]*(N+1)]+[[float('inf')]*(N+1)for _ in range(v_max)]
for v in range(1,v_max+1):
    for n in range(1,N+1):
        dp[v][n]=min((dp[v][n-1],dp[v-wv[n][1]][n-1]+wv[n][0]))

print(max(v for v in range(v_max+1) if dp[v][N]<=W))

Submission status: Time Limit Exceeded

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from random import randint

from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count

def g():
    return -1

def ifvalid(i):
    if i<0:
        return False
    return True

import sys
sys.setrecursionlimit(10**6)

def f(i,w):
    if i==-1:
        return 0

    if d[(i,w)]!=-1:
        return d[(i,w)]

    if ifvalid(w - ar[i][0]):
        d[(i,w)] = max(f(i-1,w),f(i-1,w-ar[i][0])+ar[i][1])
    else:
        d[(i,w)] = f(i-1,w)

    return d[(i,w)]



d=defaultdict(g)
n,W=sep()
ar=[]
for _ in range(n):
    ar.append(lis())
print(f(n-1,W))

Submission status: Time Limit Exceeded

Solution code:
n,W=list(map(int,input().split()))
 
dp=[[float('inf')]*(10**3*100) for _ in range(n+1)]
dp[0][0]=0
def process(dp):
    for i in range(1,n+1):
        w,v=list(map(int,input().split()))
        for j in range(0,10**3*100):
            if j<v:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=min(dp[i-1][j-v]+w,dp[i-1][j])
    for i,j in enumerate(reversed(dp[n])):
        if j<=W:
            print(10**3*100-i-1)
            break
            
process(dp)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    #start here
    n, W = map(int,input().split())
    if (W > 10**5+1):
        ans = 0
        for i in range(n):
            w, v = map(int,input().split())
            ans+=v
        print(ans)
    l = []
    dp = [[0 for i in range(W+1)] for j in range(n)]
    for i in range(n):
        w, v = map(int,input().split())
        for j in range(1, W+1):
            if(w>j):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], v+dp[i-1][j-w])
    print(dp[n-1][W])
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    #start here
    n, W = map(int,input().split())
    l = []
    dp = [[0 for i in range(W+1)] for j in range(n)]
    for i in range(n):
        w, v = map(int,input().split())
        for j in range(1, W+1):
            if(w>j):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], v+dp[i-1][j-w])
    print(dp[n-1][W])
solve()

Submission status: Time Limit Exceeded

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

V = sum([wv[i][1] for i in range(N)])

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

Submission status: Time Limit Exceeded

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

INF = 10**9+1

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

for i in range(N):
    for j in range(V):
        if j >= wv[i][1]:
            DP[i+1][j] = min(DP[i][j], DP[i][j-wv[i][1]]+wv[i][0])
        else:
            DP[i+1][j] = min(DP[i][j], wv[i][0])
        
ans = 0
for i in range(N+1):
    for j in range(V+1):
        if DP[i][j] <= W:
            ans = max(ans, j+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


import numpy as np

N, W_max = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)

'''
dp[i,j] ... 重さの最小 (:iまで考慮したとき、価値がちょうどjのとき)
答えはW以下の数字が入ってるマスの一番左側

更新則
chmin(dp[i+1,j+V[i]] , dp[i, j]+W[i]) #ナップサックに入れた場合
chmin(dp[i+1,j] , dp[i, j]) # ナップサックに入れなかった場合
'''


def solve(N, W_max, W, V):
    V_max = np.sum(V) + 1
    dp = np.full((N + 1, V_max), 10**12, dtype=np.int64)
    # 初期化
    dp[0][0] = 0  # 一個も選ばず価値が0なら必ず重さも0

    # 更新
    for i in range(N):
        for j in range(V_max):
            jv = j + V[i]
            if jv < V_max:
                dp[i + 1, jv] = min(dp[i + 1, jv], dp[i, j] + W[i])
            dp[i + 1, j] = min(dp[i + 1, j], dp[i, j])

    # 左から見てく
    for j in range(V_max - 1, -1, -1):
        if np.any(dp[:, j] <= W_max):
            print(j)
            return


solve(N, W_max, W, V)

Submission status: Time Limit Exceeded

Solution code:
import math

n, w = map(int, input().split())
weights = []
costs = []
for i in range(n):
    a,b = map(int, input().split())
    weights.append(a)
    costs.append(b)
dp = [[0 for i in range(w+1)] for i in range(n)]
for i in range(w+1):
    if(i>= weights[0]):
        dp[0][i] = costs[0]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 7)

n, w = map(int, input().split())
weights, values = [], []

for _ in range(n):
    wi, vi = map(int, input().split())
    
    weights.append(wi)
    values.append(vi)  

@lru_cache(maxsize=1024)
def f(w, n):
    # if (w, n) in cache:
        # return cache[(w, n)]
    
    if w == 0 or n == 0:
        # cache[(w, n)] = 0
        return 0
    
    if w < weights[n-1]:
        return f(w, n-1)

    
    return max(f(w, n-1), f(w-weights[n-1], n-1) + values[n-1])

# print(f.cache_info())
print(f(w, len(weights)))

Submission status: Time Limit Exceeded

Solution code:
import math
def main():
    dpt = [math.inf] * (10**3*N + 1)
    dpt[0] = 0
    for w, v in items:
        for i in range(len(dpt)-1, v-1, -1):
            dpt[i] = min(dpt[i], dpt[i-v]+w)

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





if __name__ == '__main__':
    N, W = map(int, input().split())
    items = [list(map(int, input().split())) for i in range(N)]
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
import numba as nb 

@nb.njit()
def solve(n,w,weights, values):
	dp = [[0 for _ in range(w+1)] for k in range(n+1)]
	for i in range(1,n+1):
		for j in range(1,w+1):
			if weights[i] <= j:
				dp[i][j] = max(dp[i-1][j],
			   	dp[i-1][j-weights[i]] + values[i])
			else:
				dp[i][j] = dp[i-1][j]
	return dp[n][w]

def main():
	n, w = map(int, stdin.readline().split())
	values = []
	weights = []

	for _ in range(n):
		v,a = map(int, stdin.readline().split())
		values.append(a)
		weights.append(v)

	values = [0] + values
	weights = [0] + weights
	print(solve(n,w,weights,values))

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
n,mw=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[[float('inf') for _ in range(10**5+10)]for _ in range(n+1)]
#dp[i][j]=i個目までの品物を選んだとき、価値をjにする最小の重さ
dp[0][0]=0
for i in range(n):
    w,v=l[i]
    for j in range(10**5+10):
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        if j+v<10**5+10:
            dp[i+1][j+v]=min(dp[i+1][j+v],dp[i][j]+w)
    for j in range(10**5+9):
        dp[i+1][-2-j]=min(dp[i+1][-2-j],dp[i+1][-1-j])
for i in range(10**5+10):
    if dp[-1][i]>mw:
        print(i-1)
        break

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
n, w = map(int, input().split())
wht = [0]*n
val = wht.copy()
sum_value = 0
for i in range(n):
    wht[i], val[i] = map(int, input().split())
    sum_value+=val[i]
    #print(wht, val)
import math
ans = [float(math.inf)]*(sum_value+1)
ans[0] = 0
for i in range(n):
    for j in range(0, ((sum_value-val[i])+1))[::-1]:
        ##print(j, wht, val, ans)
        ans[j+val[i]]=min(ans[j+val[i]], ans[j]+wht[i])
#print(ans)
fans = 0
for i in range(0, ((sum_value)+1))[::-1]:
    if ans[i]<=w:
        fans = max(fans, i)
print(fans)

Submission status: Time Limit Exceeded

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
    
def fun(A,P,W,N,dp):
    if N == 0 or W == 0:
        return 0
    if dp.get((W,N),-1) != -1:
        return dp[(W,N)]
    else:
        if A[N-1] <= W:
            dp[(W,N)]  = max(P[N-1] + fun(A,P,W-A[N-1],N-1,dp) , fun(A,P,W,N-1,dp))
        else:
            dp[(W,N)] =  fun(A,P,W,N-1,dp)
        return dp[(W,N)]
    
    
N,W = ilele()
P = []
A = []
for i in range(N):
    a,b =ilele()
    A.append(a)
    P.append(b)
dp = {}
print(fun(A,P,W,N,dp))

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int, input().split())
v_max = (10**3)*(N+1)
inf = float('inf')
dp = [inf for _ in range(v_max+1)]
dp[0] = 0
for _ in range(N):
	w,v = map(int, input().split())
	for j in range(v_max,-1,-1):
		if j==0:
			dp[j] = 0
		else:
			a = dp[j]
			b = w + dp[j-v]		
			if v>j:
				dp[j] = a
			else:
				dp[j] = min(a,b)
ans = None
for i in range(v_max,-1,-1):
	z = dp[i]
	if z<=W and z!=inf:
		ans = i
		break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int, input().split())
v_max = 10**5
inf = float('inf')
dp = [inf for _ in range(v_max+1)]
dp[0] = 0
for _ in range(N):
	w,v = map(int, input().split())
	for j in range(v_max,-1,-1):
		if j==0:
			dp[j] = 0
		else:
			a = dp[j]
			b = w + dp[j-v]		
			if v>j:
				dp[j] = a
			else:
				dp[j] = min(a,b)
ans = None
for i in range(v_max,-1,-1):
	z = dp[i]
	if z<=W and z!=inf:
		ans = i
		break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
	N,W = map(int, input().split())
	dp = [0 for _ in range(W+1)]
	for _ in range(N):
		w,v = map(int, input().split())
		for i in range(W,0,-1):
			if i>=w:
				a = dp[i]
				b = dp[i-w]+v
				if a>b:
					dp[i] = a
				else:
					dp[i] = b
		
	print(dp[-1])
 
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)]

#i個目を選ぶとき合計価値がjになる場合の重さの最小値
#(i-1,j)  or  (i-1,j-v)+w

dp = [[10**12-1]*100010 for i in range(N)]

dp[0][WV[0][1]] = WV[0][0]
res = WV[0][1]

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

Submission status: Time Limit Exceeded

Solution code:

#Atcoder#D - Knapsack 1
#{TLE -4 passed} due to python 

#knapsack - errichto method - super super good

n,cap = list(map(int,input().split()))
sum_value = 0
items = []
for _ in range(n):
    item = list( map(int,input().split()) )
    items.append(item)
    sum_value += item[1]
INF = float('inf')
dp = [INF]*(sum_value+1)
dp[0] = 0 #
for item in items:
    weight,value= item
    for j in range(sum_value - value,-1,-1):
        dp[j+value] = min(dp[j+value] , dp[j] + weight)
res = 0
for value,weight in enumerate(dp):
    if weight <= cap and value>res:
        res = value
print(res)

Submission status: Time Limit Exceeded

Solution code:
#import
#import math
#import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

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

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

dp[0][0] = 0

#  i:N個目 j:価値

for i, (w, v) in enumerate(x, 1):
    for j in range(10**5 + 1):
        dp[i][j] = dp[i - 1][j]
        if j != 0 and v <= j:
            dp[i][j] = min(dp[i][j], dp[i - 1][j - v] + w)

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

Submission status: Time Limit Exceeded

Solution code:
n,w=[int(i) for i in input().split()]
wi=[]
val=[]
for i in range(n):
    a,b=[int(i) for i in input().split()]
    wi.append(a)
    val.append(b)
tot=sum(val)
dp=[float("inf") for i in range(tot+1)]
dp[0]=0
for i in range(n):
    for j in range(tot-val[i],-1,-1):
        dp[j+val[i]]=min(dp[j+val[i]],dp[j]+wi[i])
ans=0
for i in range(len(dp)):
    if dp[i]<=w:
        ans=max(ans,i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
x,size=map(int,input().split())
weight=[]
value=[]
for i in range(x):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[0 for i in range(size+1)] for j in range(len(weight))]
for i in range(len(weight)):
    dp[i][0]=0
for i in range(len(weight)):
    for j in range(1,size+1):
        if weight[i]>j:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
print(dp[len(value)-1][size])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import Counter
n,W = map(int,stdin.readline().split())
dp = Counter({0:0})
for _ in range(n):
    w,v = map(int,stdin.readline().split())
    r = dp.copy()
    for i in r:
        if i+w <= W:
            dp[i+w] = max(r[i+w],r[i]+v)
print(dp[max(dp,key=dp.get)])

Submission status: Time Limit Exceeded

Solution code:
import scipy.optimize
import copy

def bunri(c,A,b,x_bounds):
    sr=scipy.optimize.linprog(c,A_ub=A,b_ub=b,bounds=x_bounds,method="revised simplex")
    return sr,x_bounds

n,w=map(int,input().split())
a=[[int(i) for i in input().split()] for _ in range(n)]
c=[]
A=[]
b=[w]
l=[]
for x in a:
    c.append(-x[1])
    l.append(x[0])
A.append(l)
x_bounds=[(0,1)]*len(c)

res_list=[]
res_list.append(bunri(c,A,b,x_bounds))

m=10000
while len(res_list)>0:
    pop_res,x_bounds=res_list.pop(0)
    if pop_res["success"]==False:continue
    rx=pop_res["x"]
    for i,num in enumerate(rx):
        if 0<num<1:
            index=i
            break
    else:
        m=min(m,int(pop_res["fun"]))
        continue

    x_bounds[index]=(1,1)
    res_list.append(bunri(c,A,b,copy.deepcopy(x_bounds)))
    
    x_bounds[index]=(0,0)
    res_list.append(bunri(c,A,b,copy.deepcopy(x_bounds)))

print(-m)

Submission status: Time Limit Exceeded

Solution code:
import sys


def resolve():
    readline = sys.stdin.readline

    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for x in [0] * N]

    # 配るDP
    # dp[i][sum_v]はi個の品物の内でsum_v以上となる最小の重量
    V = N * 10 ** 3 + 1  # 価値の最大値
    inf = 10 ** 10
    dp = [[inf] * V for _ in [0] * (N + 1)]
    dp[0][0] = 0

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

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

resolve()

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
val=[0]*(n)
wt=[0]*(n)
for i in range(n):
    wt[i],val[i]=map(int,input().split()) 
dp=[[0 for i in range(w+1)] for j in range(n+1)]
for i in range(1,n+1):
    for j in range(1,w+1):
        if j>=wt[i-1]:
            dp[i][j]=max(dp[i-1][j],val[i-1]+dp[i-1][j-wt[i-1]])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][w])

Submission status: Time Limit Exceeded

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

def main():
  
  def knapsack_price(single=True):
    V = sum(price_list)
    dp_max = W + 1
    dp = [dp_max] * (V+1)
    dp[0] = 0
    
    for i in range(N):
      if single:
        S = list(reversed(range(price_list[i], V+1)))
      else:
        S = list(range(price_list[i], V+1))
      for price in S:
        dp[price] = min(dp[price], dp[price - price_list[i]] + weight_list[i])
    
    return max(price for price in range(V+1) if dp[price] <= W)
  
  N,W = map(int,input().split())
  
  price_list = []
  weight_list = []
  for _ in range(N):
    weight, price = map(int,input().split())
    price_list.append(price)
    weight_list.append(weight)
    
  print(knapsack_price(single=True))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

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