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^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

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

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

5000000000

The answer may not fit into a 32-bit integer type.

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 i in range(N):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)

dp = [[0]*(W+1) for j in range(N+1)] # DPテーブルの作成

for i in range(N):
    for j in range(W+1):
        if j < w[i]: # 選ばない時
            dp[i+1][j] = dp[i][j]
        else: # 選ぶ時
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, w = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(n)]

dp = [[0]*(w+8) for _ in range(n+10)]
weight = [0] * (n)
value = [0] * (n)

for i in range(n):
    weight[i] = li[i][0]
    value[i] = li[i][1]

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

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
import sys

n,w=map(int,input().split())
wt,p=[],[] 
cache=[[-1 for i in range(n+1)] for i in range(w+1)]

def knapsack(W,n):
  if n==0 or W==0 :
    return 0
  elif cache[W][n] != -1:
    return cache[W][n]
  
  else:
    if wt[n-1]<=W:
      cache[W][n]=max(knapsack(W,n-1),p[n-1]+knapsack(W-wt[n-1],n-1))
      
    else:
      cache[W][n]=knapsack(W,n-1)
    
    return cache[W][n]


for _ in range(n):
  temp_wt,temp_pr=map(int,input().split())
  wt.append(temp_wt)
  p.append(temp_pr)
print(knapsack(w,n))

Submission status: Time Limit Exceeded

Solution code:
N, W = [int(i) for i in input().split()]
weight = [0]
value = [0]
for _ in range(N):
    temp1, temp2 = [int(i) for i in input().split()]
    weight.append(temp1)
    value.append(temp2)

dp = [[0] * (W + 1) for N in range(N + 1)]
#%%
for i in range(1, N + 1):
    for j in range(1, W + 1):
        if weight[i] <= j:
            dp[i][j] = max(value[i] + dp[i - 1][j - weight[i]] , dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

n,w=map(int,input().split())
wt,p=[],[] 
cache=[[-1 for i in range(n+1)] for i in range(w+1)]

def knapsack(W,n):
  if n==0 or W==0 :
    return 0
  elif cache[W][n] != -1:
    return cache[W][n]
  
  else:
    if wt[n-1]<=W:
      cache[W][n]=max(knapsack(W,n-1),p[n-1]+knapsack(W-wt[n-1],n-1))
      
    else:
      cache[W][n]=knapsack(W,n-1)
    
    return cache[W][n]


for _ in range(n):
  temp_wt,temp_pr=map(int,input().split())
  wt.append(temp_wt)
  p.append(temp_pr)
print(knapsack(w,n))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

n,w=map(int,input().split())
wt,p=[],[] 
cache=[[-1]*(n+1) for i in range(w+1)]

def knapsack(W,n):
  if n==0 or W==0 :
    return 0
  elif cache[W][n] != -1:
    return cache[W][n]
  
  else:
    if wt[n-1]<=W:
      cache[W][n]=max(knapsack(W,n-1),p[n-1]+knapsack(W-wt[n-1],n-1))
      
    else:
      cache[W][n]=knapsack(W,n-1)
    
    return cache[W][n]


for _ in range(n):
  temp_wt,temp_pr=map(int,input().split())
  wt.append(temp_wt)
  p.append(temp_pr)
print(knapsack(w,n))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
wt,p=[],[] 
cache=[[-1]*101 for i in range(100001)]

def knapsack(W,n):
  if n==0 or W==0 :
    return 0
  elif cache[W][n] != -1:
    return cache[W][n]
  
  else:
    if wt[n-1]<=W:
      cache[W][n]=max(knapsack(W,n-1),p[n-1]+knapsack(W-wt[n-1],n-1))
      
    else:
      cache[W][n]=knapsack(W,n-1)
    
    return cache[W][n]

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

for _ in range(n):
  temp_wt,temp_pr=map(int,input().split())
  wt.append(temp_wt)
  p.append(temp_pr)
print(knapsack(w,n))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
wt,p=[],[] 
cache=[[-1]*101 for i in range(100001)]

def knapsack(W,n):
  if n==0 or W==0 :
    return 0
  elif cache[W][n] != -1:
    return cache[W][n]
  
  else:
    if wt[n-1]<=W:
      cache[W][n]=max(knapsack(W,n-1),p[n-1]+knapsack(W-wt[n-1],n-1))
      
    else:
      cache[W][n]=knapsack(W,n-1)
    
    return cache[W][n]

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

for _ in range(n):
  temp_wt,temp_pr=map(int,input().split())
  wt.append(temp_wt)
  p.append(temp_pr)
print(knapsack(w,n))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
wt,p=[],[] 
cache=[[-1]*101 for i in range(100001)]

def knapsack(W,n):
  if n==0 or W==0 :
    return 0
  elif cache[W][n] != -1:
    return cache[W][n]
  
  else:
    if wt[n-1]<=W:
      cache[W][n]=max(knapsack(W,n-1),p[n-1]+knapsack(W-wt[n-1],n-1))
      
    else:
      cache[W][n]=knapsack(W,n-1)
    
    return cache[W][n]

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

for _ in range(n):
  temp_wt,temp_pr=map(int,input().split())
  wt.append(temp_wt)
  p.append(temp_pr)
print(knapsack(w,n))

Submission status: Time Limit Exceeded

Solution code:
  
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    def knapsack(W,n):     
  
        # base conditions 
        if n == 0 or W == 0: 
            return 0
        if t[n][W] != -1: 
            return t[n][W] 
    
        # choice diagram code 
        if wt[n-1] <= W: 
            t[n][W] = max( val[n-1] + knapsack(W-wt[n-1], n-1),  knapsack(W, n-1)) 
            return t[n][W] 
        elif wt[n-1] > W: 
            t[n][W] = knapsack( W, n-1) 
            return t[n][W] 
    
    
        
    wt,val=[],[]
    n,w=map(int,input().split())
    t=[[-1 for i in range(w+1)]for j in range(n+1)]
    for _ in range(n):
        temp_wt,temp_pr=map(int,input().split())
        wt.append(temp_wt)
        val.append(temp_pr)
    print(knapsack(w,n))
    


# region fastio

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)

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

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def knapsack(W,n):     
  
    # base conditions 
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
  
    # choice diagram code 
    if wt[n-1] <= W: 
        t[n][W] = max( val[n-1] + knapsack(W-wt[n-1], n-1),  knapsack(W, n-1)) 
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapsack( W, n-1) 
        return t[n][W] 
  

    
wt,val=[],[]
n,w=map(int,input().split())
t=[[-1 for i in range(w+1)]for j in range(n+1)]
for _ in range(n):
    temp_wt,temp_pr=map(int,input().split())
    wt.append(temp_wt)
    val.append(temp_pr)
print(knapsack(w,n))

Submission status: Time Limit Exceeded

Solution code:
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def knapsack(W,n):
  if n==0 or W==0 :
    return 0
  elif cache.get((W,n)):
    return cache[(W,n)]
  
  else:
    if wt[n-1]<=W:
      cache[(W,n)]=max(knapsack(W,n-1),p[n-1]+knapsack(W-wt[n-1],n-1))
      return cache[(W,n)]
    else:
      cache[(W,n)]=knapsack(W,n-1)
      return cache[(W,n)]
    
wt,p=[],[]
cache={}
def main():
    n,w=map(int,input().split())
    
    for _ in range(n):
      temp_wt,temp_pr=map(int,input().split())
      wt.append(temp_wt)
      p.append(temp_pr)
    print(knapsack(w,n))

# region fastio

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)

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

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
def knapsack(W,n):
  if n==0 or W==0 :
    return 0
  elif cache.get((W,n)):
    return cache[(W,n)]
  
  else:
    if wt[n-1]<=W:
      cache[(W,n)]=max(knapsack(W,n-1),p[n-1]+knapsack(W-wt[n-1],n-1))
      return cache[(W,n)]
    else:
      cache[(W,n)]=knapsack(W,n-1)
      return cache[(W,n)]
    
wt,p=[],[]
cache={}
def main():
    n,w=map(int,input().split())
    
    for _ in range(n):
      temp_wt,temp_pr=map(int,input().split())
      wt.append(temp_wt)
      p.append(temp_pr)
    print(knapsack(w,n))


# region fastio

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


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
wt,p=[],[]
cache={}
def knapsack(W,n):
  if n==0 or W==0 :
    return 0
  elif cache.get((W,n)):
    return cache[(W,n)]
  
  else:
    if wt[n-1]<=W:
      cache[(W,n)]=max(knapsack(W,n-1),p[n-1]+knapsack(W-wt[n-1],n-1))
      
    else:
      cache[(W,n)]=knapsack(W,n-1)
    
    return cache[(W,n)]

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

for _ in range(n):
  temp_wt,temp_pr=map(int,input().split())
  wt.append(temp_wt)
  p.append(temp_pr)
print(knapsack(w,n))

Submission status: Time Limit Exceeded

Solution code:
def ks(n,c,dp):
    if(dp[n][c]!="undef"):
        return dp[n][c]
    if(n==0 or c==0):
        result=0
    elif(c-w[n-1]<0):
        result=ks(n-1,c,dp)
    else:
        t1=ks(n-1,c,dp)
        t2=v[n-1]+ks(n-1,c-w[n-1],dp)
        result=max(t1,t2)
    dp[n][c]=result
    return result

n,c=list(map(int,input().split()))
w=[]
v=[]
for i in range(n):
    wei,val=map(int,input().split())
    w.append(wei)
    v.append(val)
dp=[["undef" for i in range(c+1)] for j in range(n+1)]
print(ks(n,c,dp))

Submission status: Time Limit Exceeded

Solution code:
def ks(n,c,dp):
    if(dp[n][c]!="undef"):
        return dp[n][c]
    if(n==0 or c==0):
        return 0
    elif(c-w[n-1]<0):
        return ks(n-1,c,dp)
    else:
        t1=ks(n-1,c,dp)
        t2=v[n-1]+ks(n-1,c-w[n-1],dp)
        res=max(t1,t2)
        dp[n][c]=res
        return res

n,c=list(map(int,input().split()))
w=[]
v=[]
for i in range(n):
    wei,val=map(int,input().split())
    w.append(wei)
    v.append(val)
dp=[["undef" for i in range(c+1)] for j in range(n+1)]
print(ks(n,c,dp))

Submission status: Time Limit Exceeded

Solution code:
def ks(n,c,dp):
    if(dp[n][c]!="undef"):
        return dp[n][c]
    if(n==0 or c==0):
        return 0
    elif(c-w[n-1]<0):
        return ks(n-1,c,dp)
    else:
        t1=ks(n-1,c,dp)
        t2=v[n-1]+ks(n-1,c-w[n-1],dp)
        res=max(t1,t2)
        return res

n,c=list(map(int,input().split()))
w=[]
v=[]
for i in range(n):
    wei,val=map(int,input().split())
    w.append(wei)
    v.append(val)
dp=[["undef" for i in range(c+1)] for j in range(n+1)]
print(ks(n,c,dp))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
value, weight = [0], [0]
for _ in range(N):
  w, v = map(int, input().split())
  weight.append(w)
  value.append(v)
dp = [[-1]*(W+1) for _ in range(N+1)]
dp[0][0] = 0

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

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
W, V = [], []
sum_w = 0
for i in range(n):
  wi, vi = map(int ,input().split())
  W.append(wi)
  V.append(vi)
  sum_w += wi

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

for i in range(n):
  for w_i in range(w + 1):
    memo[i+1][w_i] = max(memo[i+1][w_i], memo[i][w_i])
    if w_i - W[i] >= 0:
      memo[i+1][w_i] = max(memo[i+1][w_i], memo[i][w_i-W[i]] + V[i])
print(memo[-1][-1])

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+1)] for _ in range(N+1)]

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

Submission status: Time Limit Exceeded

Solution code:
def dp(n,W,w,p,cache):
  
  if n==0 or W==0:
    return 0
  elif cache.get((n,W)):
    return cache[(n,W)]
  else:
    if w[n-1]<=W:
      cache[(n,W)]=max(p[n-1]+dp(n-1,W-w[n-1],w,p,cache),dp(n-1,W,w,p,cache))
      return cache[(n,W)]
    else:
      cache[(n,W)]=dp(n-1,W,w,p,cache)
      return cache[(n,W)]
n,W=map(int,input().split())
weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p)
print(dp(n,W,weight,profit,dict()))

Submission status: Time Limit Exceeded

Solution code:
n,W=map(int,input().split())
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
def dp(n,W,w,p):
  
  if n==0 or W==0:
    return 0
  elif t[n][W]!=-1:
    return t[n][W]
  else:
    if w[n-1]<=W:
      t[n][W]=max(p[n-1]+dp(n-1,W-w[n-1],w,p),dp(n-1,W,w,p))
    else:
      t[n][W]=dp(n-1,W,w,p)
    return t[n][W]

weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p)
print(dp(n,W,weight,profit))

Submission status: Time Limit Exceeded

Solution code:
cache={}
def dp(n,W,w,p):
  
  if n==0 or W==0:
    return 0
  elif (n,W) in cache:
    return cache[(n,W)]
  else:
    if w[n-1]<=W:
      cache[(n,W)]=max(p[n-1]+dp(n-1,W-w[n-1],w,p),dp(n-1,W,w,p))
    else:
      cache[(n,W)]=dp(n-1,W,w,p)
    return cache[(n,W)]
n,W=map(int,input().split())
weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p)
print(dp(n,W,weight,profit))

Submission status: Time Limit Exceeded

Solution code:
def dp(n,W,w,p,cache):
  
  if n==0 or W==0:
    return 0
  elif cache.get((n,W)):
    return cache[(n,W)]
  else:
    if w[n-1]<=W:
      cache[(n,W)]=max(p[n-1]+dp(n-1,W-w[n-1],w,p,cache),dp(n-1,W,w,p,cache))
    else:
      cache[(n,W)]=dp(n-1,W,w,p,cache)
    return cache[(n,W)]
n,W=map(int,input().split())
weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p)
print(dp(n,W,weight,profit,dict()))

Submission status: Time Limit Exceeded

Solution code:
def dp(n,W,w,p,cache):
  
  if n==0 or W==0:
    return 0
  elif (n,W) in cache.keys():
    return cache[(n,W)]
  else:
    if w[n-1]<=W:
      cache[(n,W)]=max(p[n-1]+dp(n-1,W-w[n-1],w,p,cache),dp(n-1,W,w,p,cache))
    else:
      cache[(n,W)]=dp(n-1,W,w,p,cache)
    return cache[(n,W)]
n,W=map(int,input().split())
weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p)
print(dp(n,W,weight,profit,dict()))

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
W=[]
V=[]
for _ in range(n):
    x,y=map(int,input().split())
    W.append(x)
    V.append(y)
dp=[[0]*(w+1) for _ in range(n+1)]

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

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
dp = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
    w, v = map(int, input().split())
    for w_lim in range(W+1):
        if w <= w_lim:
            dp[i+1][w_lim] = max(dp[i][w_lim-w]+v, dp[i][w_lim])
        else:
            dp[i+1][w_lim] = dp[i][w_lim]
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
ans = [0]*(w+1)
for i in range(n):
    wht, val = map(int, input().split())
    for j in range(0, ((w-wht)+1))[::-1]:
        #print(j, wht, val, ans)
        ans[j+wht]=max(ans[j+wht], ans[j]+val)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
def main():

    N, W = map(int, input().split())
    knap = []

    for i in range(N):
        knap.append(list(map(int, input().split())))
    
    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 >= knap[i][0]):
                dp[i+1][j] = max(dp[i][j], dp[i][j-knap[i][0]]+knap[i][1])
            else:
                dp[i+1][j] = dp[i][j]

    print(dp[N][W])
main()

Submission status: Time Limit Exceeded

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

for i in range(N):
    knap.append(list(map(int, input().split())))
    
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 >= knap[i][0]):
            dp[i+1][j] = max(dp[i][j], dp[i][j-knap[i][0]]+knap[i][1])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
dp=[0]*(W+1)
# dp[w] := 上限の容量wのときの価値の最大値

for i in range(1,N+1):
    w,v=map(int,input().split())
    for j in reversed(range(w,W+1)):
        dp[j]=max(dp[j-w]+v, dp[j])
    
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(N+1)]
# dp[n][w] := n個の品物のうち上限の容量wのときの価値の最大値

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, W = map(int, input().split())
    L = [list(map(int, input().split())) for i in range(N)]
    #もらうDP i+1が i番目を検討した結果を示す
    V = [[0]*(W+1) for i in range(N+1)]

    for i in range(N):
        w, v = L[i]
        for s in range(W+1):
            if s-w >=0:
                #選んだあとの価値
                V[i+1][s] = max(V[i+1][s], V[i][s-w] + v)
            # 選ばないときと比較
            V[i+1][s] = max(V[i+1][s], V[i][s])
    print(V[N][W])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
dp = [0] * (W + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        tmp = dp[j-w] + v
        if tmp > dp[j]:
            dp[j] = tmp
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

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

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

import numpy as np

A = []

for i in range (0, N):
	B,C = map(int, input().split())
	A.append([B, C])

A = np.array(A)

DP = np.array([[0]*(Weight+1)]*N)

for i in range (0, Weight+1):
	if A[0][0] <= i:
		DP[0][i] = A[0][1]

for i in range (1, N):
	for j in range (0, Weight+1):
		if A[i][0] > j:
			DP[i][j] = DP[i-1][j]
		else:
			DP[i][j] = 	max(DP[i-1][j], DP[i-1][j-A[i][0]]+A[i][1])
        
print(DP[N-1][Weight])

Submission status: Time Limit Exceeded

Solution code:
import sys

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

def main():
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for _ in range(N)]
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    
    for w in range(1,W+1):
        for i in range(1,N+1):
            if w - wv[i-1][0] >= 0:
                dp[i][w] = max(dp[i-1][w],dp[i-1][w-wv[i-1][0]] + wv[i-1][1])
            else:
                dp[i][w] = dp[i-1][w]
    print(dp[-1][-1])

if __name__ == "__main__":
    main()

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:
				dp[i] = max(dp[i],dp[i-w]+v)
		
	print(dp[-1])

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

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:
			dp[i] = max(dp[i],dp[i-w]+v)
	
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

N,W = map(int, sys.stdin.buffer.readline().split())
dp = [0 for _ in range(W+1)]
for _ in range(N):
	w,v = map(int, sys.stdin.buffer.readline().split())
	for i in range(W,0,-1):
		if i-w>=0:
			dp[i] = max(dp[i],dp[i-w]+v)
	
print(dp[W])

Submission status: Time Limit Exceeded

Solution code:
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>=0:
			dp[i] = max(dp[i],dp[i-w]+v)
	
print(dp[-1])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, w = map(int, input().split())
wht = []
val = []
for i in range(n):
    a, b = map(int, input().split())
    wht.append(a)
    val.append(b)
ans = np.array([[0]*(w+1)]*n, dtype=np.int64)
#print(ans)
for i in range(0, n):
    for j in range(0, w+1):
        #print(j, i, ans)
        if i==0:
            (ans[i])[j]=0   
        if True:
            if j<wht[i]:
                (ans[i])[j]=np.int64(ans[i-1][j])
            else:
                xxx = val[i]
                yyy = int(ans[i-1][j-wht[i]])
                ##print(xxx+yyy, type(xxx), type(yyy))
                ##print(True,"sum=", val[i]+(ans[i-1][j-wht[i]]), ans[i-1][j], ans[i-1][j-wht[i]], val[i])
                #print(max(xxx+yyy,int(ans[i-1][j])))
                ans[i][j] = np.int64(max(xxx+yyy,int(ans[i-1][j])))
print(ans[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
dp = [0] * (W + 1)

for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        tmp = dp[j-w] + v
        if tmp > dp[j]:
            dp[j] = tmp
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

def main():
    n, w = map(int, input().split())
    a = np.array([list(map(int, x.split())) for x in sys.stdin.readlines()])
    dp = np.array([[0]*(w+1) for _ in range(n+1)])

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

            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    print(dp[n][w])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

def main():
    n, w = map(int, input().split())
    a = np.array([list(map(int, x.split())) for x in sys.stdin.readlines()])
    dp = np.array([[0]*(w+1) for _ in range(n+1)])

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

            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    print(dp[n][w])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    n, w = map(int, input().split())
    a = [list(map(int, x.split())) for x in sys.stdin.readlines()]
    dp = [[0]*(w+1) for _ in range(n+1)]

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

            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    print(dp[n][w])

if __name__ == '__main__':
    main()