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())
prod = [list(map(int,input().split())) for i in range(n)]

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

for i in range(1,n+1):
    for j in range(1,w+1):
        p = j-prod[i-1][0]
        dp[i][j] = dp[i-1][j]
        if(p<0):
            continue
        
        dp[i][j] = max(dp[i-1][j],dp[i-1][p]+prod[i-1][1])

print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
W, V = [], []
for i in range(n):
    wi, vi = map(int, input().split())
    W.append(wi)
    V.append(vi)
    
# Dp[i][sum_w] := i-1 番目までの品物から重さがsum_wを超えないように選んだときの、価値の総和の最大値
Dp = [[0] * (w + 1) for _ in range(n+1)]

for i in range(n):
    for sum_w in range(w+1):
        # i番目の商品を選ぶ場合
        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])
        # i番目の商品を選ばない場合
        Dp[i+1][sum_w] = max(Dp[i+1][sum_w], Dp[i][sum_w])
print(Dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,w = map(int,input().split())
wv = [tuple(map(int,input().split())) for i in range(n)]

dp = [0]*(w+1)
for i in range(n):
    for j in range(w, wv[i][0]-1, -1): #なぜ逆順にするかはdpを出力するとわかる！
        dp[j] = max(dp[j],dp[j-wv[i][0]]+wv[i][1])
    #print(dp) #品物番号ごとに出力して様子見
#通常のナップサック問題は行列で考えるが、今回は1列として品物番号ごとに更新していくスタイル。

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)] #1_indexed
for i,j in itertools.product(range(N),range(W+1)):
    w,v = wv[i]
    if j-w>=0:
        dp[i+1][j] = max(dp[i+1][j],dp[i][j-w]+v)
    dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

N, W = map(int, input().split())
L = [list(map(int,input().split())) for i in range(N)]
dp = [[0] * (W + 1) for i in range(N + 1)]

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

dp = np.zeros([N+1,W+1],dtype=int)

for i in range(N):
    weight,value = map(int, input().split())
    for sum_w in range(W+1):
        if sum_w - weight >=  0:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - weight] + value)
        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:
import sys
input = sys.stdin.readline
import numpy as np

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

dp = np.zeros([N+1,W+1],dtype=int)

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N, W = map(int, input().split())
weight_value = [LI() for i in range(N)]


dp = np.zeros([N+1,W+1],dtype=int)

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

print(dp[N][W])

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

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:
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)]

for i in range(N-1,-1,-1):# 2 1 0
    for j in range(W+1):# 0 1 2 3 4 5 6 7 8
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])

print(dp[0][W])

Submission status: Time Limit Exceeded

Solution code:
import copy
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)

d = [0]*(W+1)
dp = [copy.deepcopy(d) for j in range(N+1)]

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:
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)]

for i in range(N):# 2 1 0
    for j in range(W+1):# 0 1 2 3 4 5 6 7 8
        """
        for k in dp:
            print(k)
        print(i,j)
        print("-------------------")
        """
        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])
"""
for k in dp:
    print(k)
print("-------------------")
"""
print(dp[N][W])

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 _ in range(n+1)]
for i in range(n):
    for j in range(W+1):
        if j-w[i]>=0:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[n][W])

Submission status: Time Limit Exceeded

Solution code:
n,W,*wv=map(int,open(0).read().split())
w=wv[::2]
v=wv[1::2]
dp=[[0 for i in range(W+1)]for j in range(2)]
for i in range(n):
  t=i&1
  for j in range(W,-1,-1):
    if j<w[i]:
      dp[t][:j+1]=dp[t-1][:j+1]
      break
    else:
      dp[t][j]=max(dp[t-1][j-w[i]]+v[i],dp[t-1][j])
print(dp[(n-1)&1][-1])

Submission status: Time Limit Exceeded

Solution code:
n,W,*wv=map(int,open(0).read().split())
w=wv[::2]
v=wv[1::2]
dp=[[0 for i in range(W+1)]for j in range(2)]
for i in range(n):
  t=i&1
  for j in range(W+1):
    if j<w[i]:
      dp[t][j]=dp[t-1][j]
    else:
      dp[t][j]=max(dp[t-1][j-w[i]]+v[i],dp[t-1][j])
print(dp[(n-1)&1][-1])

Submission status: Time Limit Exceeded

Solution code:
n,W,*wv=map(int,open(0).read().split())
w=wv[::2]
v=wv[1::2]
dp=[[0 for i in range(W+1)]for j in range(n)]
for i in range(n):
  for j in range(W+1):
    if i==0:
      if j<w[i]:
        dp[i][j]=0
      else:
        dp[i][j]=v[i]
    else:
      if j<w[i]:
        dp[i][j]=dp[i-1][j]
      else:
        dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j])
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
load=[list(map(int,input().split())) for i in range(n)]
dp=[[0 for i in range(w+1)]for j in range(n)]

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

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[i][j]は、品数i,重さjのときの価値
dp =[[0 for i in range(W+1)] for j in range(N+1)] 
#表で表す

for i in range(N):#これは品数.i番目の品のオンオフ
    for j in range(W+1):#これは許容される重さの合計
        #選ぶ場合
        if j - w[i]>=0:
            dp[i+1][j]=max(dp[i][j],(dp[i][j-w[i]]+v[i]))
        #選ばない場合と比較
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8


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

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

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

Submission status: Time Limit Exceeded

Solution code:
# Knapsack 1
# https://dmoj.ca/problem/dpd
import sys
inp = sys.stdin.readline

items, capacity = map(int, inp().split())

dp = [0 for _ in range(capacity + 1)] # initialize array with 0s

for x in range(items): # for every item
    weight, value = map(int, inp().split()) # collect its respective weight and value
    
    for i in range(capacity, weight-1, -1): # backwards loop from capacity to weight-1
        if (dp[i-weight]+ value > dp[i]): # if new entry is greater than existing entry
            dp[i] = dp[i-weight] + value # reassign dp[i] with new max value 
            # print(dp)

# print highest value in the list (not necessarily the last item!)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W = map(int,input().split())
#N = int(input())
dp =[[0 for i in range(W+1)] for j in range(N+1)]
w = [0]*(N)
v = [0]*N
for i in range(N):
  w[i],v[i] =  map(int,input().split())
for i in range(N):
  for j in range(W+1):
    if (j >= w[i]):
      dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]] + v[i])
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
print(dp[N][W])

Submission status: Time Limit Exceeded

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

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

for h in range(W):
    if h+1>=w[0]:
        dp[0][h]=v[0]

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

Submission status: Time Limit Exceeded

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


wv=[list(map(int, input().split())) for i in range(n)]
dp=[[0]*(w+1) for _ in range(n)]


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



print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
Wl = []; Vl = []
for i in range(N):
    w, v = map(int, input().split())
    Wl.append(w); Vl.append(v)
# dp[i番目までの品物を使用][wを超えない]
dp = [[0]*(W+10) for _ in range(N+10)]

for i in range(N):
    w, v = Wl[i], Vl[i]
    for j in range(W+1):
        if j+w < W+1: dp[i+1][j+w] = max(dp[i+1][j+w], dp[i][j]+v)
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
n,W = [int(e) for e in input().split()]
v = list([0]*n)
w = list([0]*n)

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

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

print(dp[n][W])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    wv = [[int(x) for x in input().split()] for _ in range(N)]

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

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

    print(max(dp[-1]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W+1)] for x in range(n+1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n+1): 
        for w in range(W+1): 
            if i==0 or w==0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W] 
  
n, W = map(int, input().split()) 
val = [] 
wt = [] 

for _ in range(n):
    w, v = map(int, input().split()) 
    val.append(v)
    wt.append(w)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
  N, W = map(int, input().split())
  dp = [-1] * (W + 1)
  dp[0] = 0
  ws = []
  ps = []
  for _ in range(N):
    w, v = map(int, input().split())
    ws.append(w)
    ps.append(v)
  for i in range(len(ws)):  
    for j in range(W - ws[i], -1, -1):
      dpi = dp[j]
      if dpi != -1:
        if dp[j + ws[i]] < dpi + ps[i]:
          dp[j + ws[i]] = dpi + ps[i]
  print(max(dp))
main()

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
dp = [-1] * (W + 1)
dp[0] = 0
ws = []
ps = []
for _ in range(N):
  w, v = map(int, input().split())
  ws.append(w)
  ps.append(v)
  
for i in range(len(ws)):  
  for j in range(W - ws[i], -1, -1):
    dpi = dp[j]
    if dpi != -1:
      if dp[j + ws[i]] < dpi + ps[i]:
        dp[j + ws[i]] = dpi + ps[i]
print(max(dp))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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 = [[0]*(W+1) for _ in range(N+1)]
ret = 0
for i in range(len(weight)):
  for j in range(W+1):
    if j < weight[i]:
      DP[i+1][j] = DP[i][j]
    if j + weight[i] <= W:
      DP[i+1][j+weight[i]] = max(DP[i+1][j+weight[i]],DP[i][j]+value[i])
      ret = max(DP[i+1][j+weight[i]],ret)
print(ret)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
# dp[w] i番目までの品物で、重さがw以下になるよう選んだときの価値の最大値。
# 品物を増やすごとに、配列を更新して使いまわす。
# 重さは1~W 添え字は0<=w<=W<W+1 dpリストの長さはW+1
# ループは1~N回回す　添え字は0<=i<=N-1<N
# 添え字i, i+1回目のループでのdp[j]の求め方 i+1番目の品物を選ぶかどうか？
# j-w(i)<0のとき、重量オーバーで選べない。dp[j]は変わらない
# j-w(i)>=0のとき、dp[j]=max(dp[j], dp[j-w(i)]+v(i))
# 配列は逆側から更新していく
# 解答はN回ループした後のdp[W+1]=dp[-1] 最後の値

# 入力
# 重さと価値はループのなかで都度取得する
N, W = map(int, input().strip().split())

# 初期化
dp = [0] * (W + 1)

# dpテーブル
for i in range(N):
    w, c = map(int, input().strip().split())
    for j in range(W, -1, -1):
        if j - w >= 0:
            dp[j] = max(dp[j], dp[j - w] + c)

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    def calc(i, weight):
        iw, iv = wv[i]
        if weight -  iw >= 0:
            dp[i][weight] = max(dp[i+1][weight], dp[i+1][weight-iw] + iv)
    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 i in range(N-1, -1, -1):
        for j in range(W+1):
            calc(i, j)
    print(dp[0][W])
main()

Submission status: Time Limit Exceeded

Solution code:
# dp[w] i番目までの品物で、重さがw以下になるよう選んだときの価値の最大値。
# 品物を増やすごとに、配列を更新して使いまわす。
# 重さは1~W 添え字は0<=w<=W<W+1 dpリストの長さはW+1
# ループは1~N回回す　添え字は0<=i<=N-1<N
# 添え字i, i+1回目のループでのdp[j]の求め方 i+1番目の品物を選ぶかどうか？
# j-w(i)<0のとき、重量オーバーで選べない。dp[j]は変わらない
# j-w(i)>=0のとき、dp[j]=max(dp[j], dp[j-w(i)]+v(i))
# 配列は逆側から更新していく
# 解答はN回ループした後のdp[W+1]=dp[-1] 最後の値

# 入力
# tableは二次元配列　table[i][0]でi番目の品物の重さ、table[i][1]で価値
N, W = list(map(int, input().strip().split()))
table = []
for i in range(N):
    table.append(list(map(int, input().strip().split())))

# 初期化
dp = [0] * (W + 1)

# dpテーブル
for i in range(N):
    for j in range(W, -1, -1):
        if j - table[i][0] >= 0:
            dp[j] = max(dp[j], dp[j - table[i][0]] + table[i][1])

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    def calc(i, weight):
        w = weight -  wv[i][0]
        if w >= 0:
            v = dp[i+1][w] + wv[i][1]
            dp[i][weight] = max(dp[i+1][weight], v)
    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 i in range(N-1, -1, -1):
        for j in range(W+1):
            calc(i, j)
    print(max(dp[0]))
main()

Submission status: Time Limit Exceeded

Solution code:
def calc(i, weight, value):
    if weight > W:
        return 0
    if i == N:
        return value
    return max(calc(i+1, weight + wv[i][0], value + wv[i][1]),
               calc(i+1, weight, value))
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
print(calc(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
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 = [[0]*(W+1) for _ in range(N+1)]  

def knapsack(n,w):
  if w >W:
    return -100000000000000000000
  if n >= len(weight):
    return 0
  if DP[n][w] >0:
      return DP[n][w]
  DP[n][w] = max(knapsack(n+1,w),knapsack(n+1,w+weight[n])+value[n])
  return DP[n][w]
print(knapsack(0,0))

Submission status: Time Limit Exceeded

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

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

def knapsack(n,w):
  if w >W:
    return -1000
  if n >= len(weight):
    return 0
  return max(knapsack(n+1,w),knapsack(n+1,w+weight[n])+value[n])
print(knapsack(0,0))

Submission status: Time Limit Exceeded

Solution code:
def knapsack(weight,value,N,W,i,cache):
    if i == N or W <= 0:
        return 0
    if cache[i][W] != 0:
        return cache[i][W]
    op1,op2 = 0,0
    if weight[i] <= W:
        op1 = value[i] + knapsack(weight,value,N,W-weight[i],i+1,cache)
    op2 = knapsack(weight,value,N,W,i+1,cache)
    cache[i][W] = max(op1,op2)
    return cache[i][W]

N,W = map(int,input().split())
weight = []
value = []
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)
cache = [[0 for i in range(W+1)] for j in range(N+1)]
print(knapsack(weight,value,N,W,0,cache))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys

import fractions
import copy
import bisect
import math
import numpy as np
import itertools
from itertools import combinations_with_replacement
#import math#数学的計算はこれでいける。普通に0.5乗しても計算可能
#w=input()
from operator import itemgetter
from sys import stdin
#input = sys.stdin.readline#こっちの方が入力が早いが使える時に使っていこう
from operator import mul
from functools import reduce
from collections import Counter
#from collections import deque

#input = stdin.readline


j=0
k=0
n=3
r=1
a=[0]
#n=int(input())
#r=int(input())
#print(M)
#A=int(input())
#B=int(input())
#print(N)
"1行1つの整数を入力を取得し、整数と取得する"


#number_list=list(map(int, input().split(" ")))#数字の時
#print(number_list)
"12 21 332 とか入力する時に使う"
"1行に複数の整数の入力を取得し、整数として扱う"

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
#メモ
for i in number_list:#こっちの方がrage使うより早いらしい
    print(number_list[i-1])#

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

'''
x=[]
y=[]
for i in range(N):
    x1, y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
print(x)
print(y)
"複数行に2数値を入力する形式 x座標とy座標を入力するイメージ"
'''

'''
mixlist=[]
for i in range(N):
    a,b=input().split()
    mixlist.append((int(a),b))
print(mixlist)
"複数行にintとstrを複合して入力するやつ，今回はリスト一つで処理している"
'''

'''
#array=[input().split()for i in range(N)]
#print(type(array[0][0]))
#print(array)
"正方行列にstr型の値を入力"
'''

#brray=[list(map(int, input().split(" ")))for i in range(N)]
#print(type(brray[0][0]))
#print(brray)
'''
入力
1 2
4 5
7 8
出力結果
[[1, 2], [4, 5], [7, 8]]
'''
"列数に関して自由度の高いint型の値を入力するタイプの行列"
#以下に別解を記載
#N, M = [int(i) for i in input().split()]
'''
table = [[int(i) for i in input().split()] for m in range(m)]

print(type(N))
print(N)
print(type(M))
print(M)

print(type(table))
print(table)
'''




#s=input()
#a=[int(i) for i in s]
#print(a[0])
#print([a])
#単数値．桁ごとに分割したい．入力と出力は以下の通り
#イメージとして1桁ごとにリストに値を入れているかんじ
#intを取ると文字列分解に使える
'''
入力
1234
出力
1
[[1, 2, 3, 4]]
'''




'''
word_list= input().split(" ")
print(word_list[0])
"連続文字列の入力"
"qw er ty とかの入力に使う"
"入力すると空白で区切ったところでlistの番号が与えられる"
'''



'''
A, B, C=stdin.readline().rstrip().split()#str style 何個でもいけることが多い
print(A)
"リストではなく独立したstr型を入れるなら以下のやり方でOK"
'''


#a= stdin.readline().rstrip()
#print(a.upper())
"aという変数に入っているものを大文字にして出力"


#a,b=map(int, input().split())  #int style 複数数値入力　「A B」みたいなスペース空いた入力のとき

#なんかうまく入力されるけど
#a=[[int(i) for i in 1.strip()]for 1 in sys.stdin]
#a = [[int(c) for c in l.strip()] for l in sys.stdin]]
#print(a)
#複数行の数値を入力して正方行列を作成


##############################################################################################
##############################################################################################
#under this line explains example calculation

'''
コンビネーションの組み合わせの中身を出力する形式
for i in itertools.combinations(brray, 2)
combinationsをpermutationsにすれば順列になる
今回なら(abc133B)
入力
1 2
5 5
-2 8
出力
[[1, 2], [5, 5], [-2, 8]]
もちろん一次元リストでも使えるし
何よりiもリストのように使えるので便利
'''

#nCr combination
'''
def cmb(n,r):
    #When n < r , this function isn't valid
    r= min(n-r,r)
    #print(n,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n-r, -1))
    #flochart mul(n,n-1)=x
    #next     mul(x,n-2)........(n-r+1,n-r)
    #mul read a,b and returns a*b

    under = reduce(mul, range(1, r+1))
    #print(over, under)
    #reduce is applied mul(1,2)=2
    #next   mul(2,3)=6
    #next   mul(6,4)=4.........last(r!,r+1)=r+1!

    return over // under
    #// is integer divide
    #calc example 5C2
    #over=5*4*3
    #under=3*2*1
a = cmb(n, r)
#print(a)
'''

'''
import itertools
from itertools import combinations_with_replacement

combinationについて
以下の違いを意識しよう
combinations() p, r 長さrのタプル列、ソートされた順で重複なし

combinations_with_replacement() p, r 長さrのタプル列、ソートされた順で重複あり


使用例 　　　　　　　　　　　                  出力　　
combinations('ABCD', 2)　　　　　　　　　　　　AB AC AD BC BD CD

combinations_with_replacement('ABCD', 2)　　 AA AB AC AD BB BC BD CC CD DD
'''



'''
#集計
#example
#a=[2,2,2,3,4,3,1,2,1,3,1,2,1,2,2,1,2,1]
#a=Counter(a)
for i in a.most_common(n):print(i)
#most_common()メソッドは、出現回数が多い要素順にCounterオブジェクトを並び替えます。
#引数にint型の数字nを設定した場合は、出現回数が高い上位ｎ個の要素を返します。
#何も設定しなければ、コンテナ型にあるすべての要素を出現回数の順番に並び替えたタプル型オブジェクトを返します。
#out put
#(2, 8)
 #(1, 6)
#(3, 3)
#(4, 1)
'''


#二部探索(binary search)
#A = [1, 2, 3, 3, 3, 4, 4, 6, 6, 6, 6]
#print(A)
#index = bisect.bisect_left(A, 5) # 7 最も左(前)の挿入箇所が返ってきている
#A.insert(index, 5)
#print(index)
#print(A)
'''
bisect.bisect_left(a, x, lo=0, h=len(a))
引数
a: ソート済みリスト
x: 挿入したい値
lo: 探索範囲の下限
hi: 探索範囲の上限
(lo, hiはスライスと同様の指定方法)
bisect_leftはソートされたリストaに対して順序を保ったままxを挿入できる箇所を探索します。leftが示す通り、aにすでにxが存在している場合は、挿入箇所は既存のxよりも左側になります。また、lo, hiを指定することで探索範囲を絞り込むことも可能です。デフォルトはaの全体が探索対象です。
'''





########################################################################
########################################################################
#b2=a[:]  #1次元のときはコピーはこれで良い
#print(b2)

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b3=copy.deepcopy(a)  #2次元配列はこうコピーする
#print(b3)

def main():


    j=0
    k=0
    #n=int(input())
    #r=int(input())


    "1行1つの整数を入力を取得し、整数と取得する"
    #number_list=list(map(int, input().split(" ")))#数字の時
    #print(number_list)
    "12 21 332 とか入力する時に使う"
    "1行に複数の整数の入力を取得し、整数として扱う"
    n,w=map(int,input().split(" "))


    dp= [[0]*(w+1) for i in range(n+1)]#0からwまでのw+1回計算するから
    #print(dp)＃初期条件が入る分計算回数+1列分必要(この場合は判断すべきものの数)
    brray=[list(map(int, input().split(" ")))for i in range(n)]
    #weght valueの順番で入ってるよ
    #dp=[list(map(int,for i in range(n)]

    #brray[0][0]=[weight][value]
    #print(brray)
    for i in range(n):
        for j in range(w+1):#0からwまでのw+1回計算するから
            #print(brray[i][0], brray[i][1])#この入力大丈夫
            if j >= brray[i][0]:
                dp[i+1][j]=max(dp[i][j], dp[i][j-brray[i][0]]+brray[i][1])

            else:
                dp[i+1][j]=dp[i][j]

    print(max(dp[n][:]))
    #print(dp)#最終列がn+1列目であることに注意
    #s=input()
    #a=[int(i) for i in s]#int取るとstrでも行ける
    #print(a)
    '''
    入力
    1234
    出力
    [1, 2, 3, 4]
    '''



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# dp[i][j] i番目までの品物で、重さがj以下になるよう選んだときの価値の最大値
# 0<=i<N+1, 0<=j<W+1  i=0, j=0のときはdpはすべて0
# 初期値 dp[1] j<w1ならdp[1][j]=0, j>=w1ならdp[1][j]=v1
# dp[i+1][j]の求め方 i+1番目の品物を選ぶかどうか
# j-w(i+1)<0のとき、dp[i+1][j] = dp[i][j]
# j-w(i+1)>=0のとき、dp[i+1][j]=max(dp[i][j], dp[i][j-w(i+1)]+v(i+1))
# 解答はdp[N][W]

# 入力
# tableは二次元配列　table[i][0]でi番目の品物の重さ、table[i][1]で価値 i=0は添え字をdpとそろえるためにつけた
N, W = list(map(int, input().strip().split()))
table = [[0, 0]]
for i in range(1, N+1):
    table.append(list(map(int, input().strip().split())))


# 初期化 dpテーブルの行数はN+1, 列数はW+1
dp = [[0] * (W + 1) for i in range(N + 2)]

# 初期値 i=1
for j in range(W + 1):
    if j < table[1][0]:
        dp[1][j] = 0
    else:
        dp[1][j] = table[1][1]

# dpテーブル
for i in range(1, N):
    for j in range(W + 1):
        if j - table[i+1][0] < 0:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - table[i + 1][0]] + table[i + 1][1])

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    dd = defaultdict(int)
    dd[0] = 0
    for w, v in items:
        for tw, tv in list(dd.items()):
            if tw + w <= W:
                dd[tw + w] = max(tv + v, dd[tw + w])
    print(max(dd.values()))


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)]
#wv.sort()
dp=[[0]*(w+1) for _ in range(n)]
for i in range(1,w+1):
    if i<wv[0][0]:
        dp[0][i]=0
    else:
        dp[0][i]=wv[0][1]
for i in range(1,n):
    for j in range(1,w+1):
        if wv[i][0]>j:
            dp[i][j]=dp[i-1][j]
        else:
            wleft=j-wv[i][0]
            dp[i][j]=max(wv[i][1]+dp[i-1][wleft],dp[i-1][j])
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

def knapsack(N, W, w, v):
    dp = []
    for i in range(N + 1):
        dp.append([-1] * (W + 1))
    for i in range(N + 1):
        dp[i][0] = 0
    for i in range(W + 1):
        dp[0][i] = 0

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

for i in range(N):
    x, y = map(int, input().split())
    w.append(x)
    v.append(y)

ans = knapsack(N, W, w, v)

print(ans)

Submission status: Time Limit Exceeded

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

n, w = map(int, input().split())
item = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] + [0]*w] + [[0] + [-float("inf")]*w for _ in range(n)]
wei, val = 0, 1

for i in range(n):
    for j in range(w+1):
        if item[i][wei] <= j:
            dp[i+1][j] = max(dp[i][j], dp[i][j-item[i][wei]] + item[i][val])
        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())
x=[]
for i in range(0,n):
    temp= list(map(int,input().split()))
    x.append(temp)


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