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:
import functools


@functools.lru_cache(10**9)
def get(item, remaining_weight):
    if remaining_weight == 0:
        return 0
    elif item < 0:
        return 0
    if wv[item][0] <= remaining_weight:
        return max(get(item - 1, remaining_weight - wv[item][0]) + wv[item][1], get(item - 1, remaining_weight))
    else:
        return get(item-1, remaining_weight)
    

N, W = map(int, input().split(" "))
wv = list()
for _ in range(N):
    wv.append(list(map(int, input().split(" "))))
wv = sorted(wv, key=lambda x: x[1])

print(get(N-1, W))

Submission status: Time Limit Exceeded

Solution code:
import functools


@functools.lru_cache(10**7)
def get(item, remaining_weight):
    if remaining_weight == 0:
        return 0
    elif item < 0:
        return 0
    if wv[item][0] <= remaining_weight:
        return max(get(item - 1, remaining_weight - wv[item][0]) + wv[item][1], get(item - 1, remaining_weight))
    else:
        return get(item-1, remaining_weight)
    

N, W = map(int, input().split(" "))
wv = list()
for _ in range(N):
    wv.append(list(map(int, input().split(" "))))
wv = sorted(wv, key=lambda x: x[1])

print(get(N-1, W))

Submission status: Time Limit Exceeded

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

dp = [-1 for _ in range(W + 1)] # dp[重量の総和]:= 価値の総和
dp[0] = 0

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
DP = [[0] * (W+1) for i in range(N+1)]
for n in range(1,N+1):
  wn, vn = map(int, input().split())
  for w in range(1,W+1):
    if w >= wn:
      DP[n][w] = max(DP[n-1][w-wn] + vn, DP[n-1][w])
    else:
      DP[n][w] = DP[n-1][w]
print(DP[N][W])

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 i in range(N+1)]
for n in range(1,N+1):
  wn, vn = map(int, input().split())
  for w in range(1,W+1):
    if w >= wn:
      DP[n][w] = max(DP[n-1][w-wn] + vn, DP[n-1][w])
    else:
      DP[n][w] = DP[n-1][w]
print(DP[N][W])

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 i in range(N+1)]
for n in range(1,N+1):
  wn, vn = WV[n-1]
  for w in range(1,W+1):
    if w >= wn:
      DP[n][w] = max(DP[n-1][w-wn] + vn, DP[n-1][w])
    else:
      DP[n][w] = DP[n-1][w]
print(DP[N][W])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
weight = []
value = []
for _ in range(n):
    wi, vi = map(int, input().split())
    weight.append(wi)
    value.append(vi)
weight.append(0)
value.append(0)
dp = [[0] * (w + 1) for _ in range(n + 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:
# -*- coding: utf-8 -*-
import sys
import itertools#これは色々使える組み込み関数みたいなやつ
import math#数学的計算はこれでいける。普通に0.5乗しても計算可能
#w=input()
i=0
j=0
#N=int(input())
N, W=map(int, input().split())#intとinputの間がコンマであることに注意
w, v =[0]*N, [0]*N
#S=input()
#T=input()
#S_list=list(S)
#h_list=  list(map(int, input().split(" ")))
#M=int(input())
#drink_list = [list(map(int, input().split(" ")))for i in range(M)]
#print(T_list[1]) 
#不本意だが内包表記で二次元の空のリストを作成する
for i in range(N):
 w[i], v[i] =map(int,input().split())
#下のやつだとなんかdp内にstr型で入ってしまう
#dp=[[[0] for i in range(2)] for j in range(N+1)]
dp =[[0] *(W+1) for j in range(N+1)]
#上のやり方でやると全てのdpに値が入ってエラーがでなくなり幸せになる
i=0
j=0
#やや理解が浅く遷移図をうまく頭の中で描けていないので別解を考えるべき2019/1/5
for i in range(N):
    for j in range(W+1):
        if j >=w[i]:
            dp[i+1][j]=max(dp[i][j-w[i]]+v[i], dp[i+1][j])##ここの行のj-w[i]をあまり良くわかっていない

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def knapsack1(weight_value, w):
    cur = [0] * (w + 1)
    nxt = cur.copy()

    for weight, value in weight_value:
        for i in range(1, weight):
            nxt[i] = cur[i]
        for i in range(weight, w + 1):
            nxt[i] = max(cur[i], cur[i - weight] + value)
        cur, nxt = nxt, cur
    return cur[w]


def main():
    n, w = [int(x) for x in input().split()]
    weight_value = [None] * n
    for i in range(n):
        weight_value[i] = [int(x) for x in input().split()]
    return knapsack1(weight_value, w)


print(main())

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
ww = [0]*n
vv = [0]*n
dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(n):
  ww[i],vv[i] = map(int,input().split())      
  
for i in range(1,n+1):
  for j in range(1,w+1):
    dp[i][j] = dp[i-1][j]
    if j - ww[i-1] >= 0:
      dp[i][j] = max(dp[i][j], \
                     dp[i-1][j-ww[i-1]] + vv[i-1])        

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

Submission status: Time Limit Exceeded

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

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

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

def calc(n,w):
    if n<0:
        return 0
    if dp[n][w]>=0:
        return dp[n][w]
    cw,cv=wv[n]
    r1,r2=0,0
    r1=calc(n-1,w)
    if (cw+w)<=W:
        r2=calc(n-1,cw+w)+cv

    dp[n][w]= max([r1,r2])
    return dp[n][w]

print(calc(N-1,0))

Submission status: Time Limit Exceeded

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

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

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

def calc(n,w):
    if n<0:
        return 0
    if dp[n][w]>=0:
        return dp[n][w]
    cw,cv=wv[n]
    r1,r2=0,0
    r1=calc(n-1,w)
    if (cw+w)<=W:
        r2=calc(n-1,cw+w)+cv

    return max([r1,r2])

print(calc(N-1,0))

Submission status: Time Limit Exceeded

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

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

for i in range(n):
    for j in range(sum_w + 1):
        if j < weight[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])

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

Submission status: Time Limit Exceeded

Solution code:
N,W = (int(i) for i in input().split())
w_v = [[int(i) for i in input().split()] for i in range(N)]
memo = [[-1,-1]]*N
def knapsack(n,w):   
    if n == 1:
        if w_v[n-1][0] <= w:
            v = w_v[n-1][1]
        else:
            v = 0
    else:
        u = abs(w_v[1][0]-w_v[0][0])
        for i in range(n-1):
            if abs(w_v[i][0]-w_v[i+1][0]) <= u:
                u = abs(w_v[i][0]-w_v[i+1][0])
        if memo[n-1][0] != -1 and abs(w - memo[n-1][1]) < u:
            v = memo[n-1][0]
        elif w - w_v[n-1][0] >= 0:
            x = knapsack(n-1,w-w_v[n-1][0])[0]+w_v[n-1][1]
            y = knapsack(n-1,w)[0]
            v = max(x,y)
        else:
            v = knapsack(n-1,w)[0]
    memo[n-1] = [v,w]
    return [v,w]
print(knapsack(N,W)[0])

Submission status: Time Limit Exceeded

Solution code:
N,W = (int(i) for i in input().split())
w_v = [[int(i) for i in input().split()] for i in range(N)]
memo = [[-1,-1]]*N
def knapsack(n,w):
    if n == 1:
        if w_v[n-1][0] <= w:
            v = w_v[n-1][1]
        else:
            v = 0
    else:
        if memo[n-1][0] != -1 and w == memo[n-1][1]:
            v = memo[n-1][0]
        elif w - w_v[n-1][0] >= 0:
            x = knapsack(n-1,w-w_v[n-1][0])[0]+w_v[n-1][1]
            y = knapsack(n-1,w)[0]
            v = max(x,y)
        else:
            v = knapsack(n-1,w)[0]
    memo[n-1] = [v,w]
    return [v,w]
print(knapsack(N,W)[0])

Submission status: Time Limit Exceeded

Solution code:
N,W = (int(i) for i in input().split())
w_v = [[int(i) for i in input().split()] for i in range(N)]
def knapsack(n,w):
    if n == 1:
        if w_v[n-1][0] <= w:
            v = w_v[n-1][1]
        else:
            v = 0
    else:
        if w - w_v[n-1][0] >= 0:
            x = knapsack(n-1,w-w_v[n-1][0])+w_v[n-1][1]
            y = knapsack(n-1,w)
            v = max(x,y)
        else:
            v = knapsack(n-1,w)
    return v
print(knapsack(N,W))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, W, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wv = (map(int, input().split()) for _ in range(N))
#print(tuple(map(tuple, wv)))
dp = [0] * (W + 1)
for w, v in wv:
    for j in range(W, w-1, -1):
        dp[j] = max(dp[j], dp[j - w] + v)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
#[w,v]
#重さに対応するインデックスに価値を保存する
dp=[[0]*(w+1) for i in range(n+1)]

for i in range(n):
    for sum_w in range(1,w+1):
        if sum_w-l[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-l[i][0]]+l[i][1])
        #i番目の品を入れる場合
    
        dp[i+1][sum_w]=max(dp[i][sum_w],dp[i+1][sum_w])
        #i番目の品を入れない場合
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


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

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


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
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(1, n+1):
    w_temp, v_temp = wv[i-1]
    for j in range(1,w+1):
        if(j >= w_temp):
            dp[i][j] = max(dp[i-1][j],
                            dp[i-1][j-w_temp] + v_temp)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
# 動的計画法
#D - Knapsack 1
#https://atcoder.jp/contests/dp/tasks/dp_d
#インデックスと重さを対応させていく
N, W = list(map(int,input().split()))
item = [list(map(int,input().split())) for i in range(N)]
dp = [-1]*(W+1)
dp[0] = 0
for i in range(N):
    w = item[i][0]
    v = item[i][1]
    #print(w,v)
    for j in range(W-w,-1,-1):
        if dp[j] != -1:
            if dp[j] + v > dp[j+w]:
                dp[j+w] = dp[j] + v
        #print(dp)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,w=map(int,input().split())
    items=[]
    dp=[0 for i in range(w+1)]
    for i in range(n):
        wi,vi=map(int,input().split())
        for j in range(w-wi,-1,-1):
            dp[j+wi]=max(dp[j+wi],dp[j]+vi)
    print(max(dp))
if __name__=='__main__':
    main()

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 = [[0 for weight in range(100001)] for i in range(101)]

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

print(dp[N][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+1)]
weight = [0]
value = [0]
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    i += 1
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w - weight[i]] + value[i])
        # i 番目の品物を選ばない場合
        dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][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):
    wi, vi = map(int, input().split())
    w.append(wi)
    v.append(vi)

dp = [[0 for weight in range(100001)] for ith in range(101)]


def knapsack(ith, weight):
    if dp[ith][weight] != 0:
        return dp[ith][weight]
    if ith == N:
        return dp[ith][weight]
    if weight + w[ith] > W:
        dp[ith][weight] = knapsack(ith + 1, weight)
        return dp[ith][weight]
    else:
        dp[ith][weight] = max(
            knapsack(ith + 1, weight + w[ith]) + v[ith], knapsack(ith + 1, weight)
        )
        return dp[ith][weight]


print(knapsack(0, 0))

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 = [[0 for weight in range(100001)] for ith in range(101)]


def knapsack(ith, weight):
    if dp[ith][weight] != 0:
        return dp[ith][weight]
    if not ith < N:
        return dp[ith][weight]
    if weight + w[ith] > W:
        dp[ith][weight] = knapsack(ith + 1, weight)
        return dp[ith][weight]
    else:
        dp[ith][weight] = max(
            knapsack(ith + 1, weight + w[ith]) + v[ith], knapsack(ith + 1, weight)
        )
        return dp[ith][weight]


print(knapsack(0, 0))

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 = [[0 for i in range(100001)] for i in range(101)]


def knapsack(ith, weight):
    if dp[ith][weight] != 0:
        return dp[ith][weight]
    if not ith < N:
        return dp[ith][weight]
    if weight + w[ith] > W:
        dp[ith][weight] = knapsack(ith + 1, weight)
        return dp[ith][weight]
    else:
        dp[ith][weight] = max(
            knapsack(ith + 1, weight + w[ith]) + v[ith], knapsack(ith + 1, weight)
        )
        return dp[ith][weight]


print(knapsack(0, 0))

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,W=LI()
  w=[]
  v=[]
  dp=[[0 for _ in range(W+1)] for __ in range(n+1)]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

  for i in range(n)[::-1]:
    for j in range(W+1):

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

  return dp[0][W]

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

n,W=LI()
w=[]
v=[]
for _ in range(n):
  a,b=LI()
  w.append(a)
  v.append(b)

dp=[[-1 for _ in range(W+1)] for __ in range(n+1)]

def rec(i,j):
  if dp[i][j]>=0:
    return dp[i][j]

  if i==n:
    ret=0
  elif j<w[i]:
    ret=rec(i+1,j)
  else:
    ret=max(rec(i+1,j),rec(i+1,j-w[i])+v[i])
  dp[i][j]=ret
  return ret

def main():
  return rec(0,W)

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)

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

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

for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            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:
def func():
    N, W = map(int, input().split())
    w = [0]*N
    v = [0]*N

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

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

    for i in range(N):
        for j in range(W+1):
            if j >= w[i]:
                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])

func()

Submission status: Time Limit Exceeded

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

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

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

for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            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=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(n)]
#WV[i][0]が重さ、WV[i][1]が価値
#配るDP
dp=[[0 for i in range(w+1)] for i in range(n+1)]
#dp[i][j]はi回目(0,n-1)に重さjまで入るmax value
for i in range(n):
    for j in range(w+1):
        if WV[i][0]+j<=w and i <=n-1:
            dp[i+1][j+WV[i][0]]=max(dp[i][j+WV[i][0]], dp[i][j]+WV[i][1])
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        else:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
print(max(dp[n]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,w=map(int,input().split())
cos=[0]*(w+1)
for i in range(n):
 w1,v1=map(int,input().split())
 for j in range(w,w1-1,-1):
  f=cos[j-w1]+v1
  if(cos[j]<f):
   cos[j]=f
print(cos[-1])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
cos=[0]*(w+1)
for i in range(n):
 w1,v1=map(int,input().split())
 for j in range(w,w1-1,-1):
  f=cos[j-w1]+v1
  if(cos[j]<f):
   cos[j]=f
print(cos[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
def bknap(curw,wei,val,n):
 if(n==0 or curw==0):
  return 0
 if(wei[n-1]>curw):
  return bknap(curw,wei,val,n-1)
 else:
  return max(val[n-1]+bknap(curw-wei[n-1],wei,val,n-1),bknap(curw,wei,val,n-1))
n,w=map(int,input().split())
wei=[]
val=[]
for i in range(n):
 w1,v1=map(int,input().split())
 wei.append(w1)
 val.append(v1)
print(bknap(w,wei,val,n))

Submission status: Time Limit Exceeded

Solution code:
def bknap(W, wt, val, n): 
 K = [[0 for x in range(W + 1)] for x in range(n + 1)] 
 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())
wei=[]
val=[]
for i in range(n):
 w1,v1=map(int,input().split())
 wei.append(w1)
 val.append(v1)
print(bknap(w,wei,val,n))

Submission status: Time Limit Exceeded

Solution code:
def bknap(curw,wei,val,n):
 if(n==0 or curw==0):
  return 0
 if(wei[n-1]>curw):
  return bknap(curw,wei,val,n-1)
 else:
  return max(val[n-1]+bknap(curw-wei[n-1],wei,val,n-1),bknap(curw,wei,val,n-1))
n,w=map(int,input().split())
wei=[]
val=[]
for i in range(n):
 w1,v1=map(int,input().split())
 wei.append(w1)
 val.append(v1)
print(bknap(w,wei,val,n))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

n,W = map(int, input().split())
days = []
for _ in range(n):
    day = list(map(int, input().split()))
    days.append(day)
dp = [[1000000] * (W+1) for _ in range(n)]

# # 1日目
# dp[0][0] = days[0][0]
# dp[0][1] = days[0][1]
# dp[0][2] = days[0][2]


# for d in range(1,n):
#     for i in range(3):
#         mx = 0
#         for j in range(3):
#             if i != j:
#                 mx = max(dp[d-1][j] + days[d][i],mx)
#                 # mx = max(dp[d][i], dp[d-1][j]+ days[d][i])
#         dp[d][i] = mx
# print(max(dp[-1]))

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

Submission status: Time Limit Exceeded

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
import datetime
import itertools
import sys
import copy

# 入力
#N = int(input())
#S = str(input())
#N, A, B = map(int, input().split())

N, W = map(int, input().split())
H = []
for _ in range(N) :
  H.append(list(map(int, input().split())))
#print(H)

#N(i+1)個目の品物を追加したときにWjとなる場合のWj地点の最大価値
dp = [0 for _ in range(W+1)]

for i in range(N) :
  dptemp = copy.deepcopy(dp)
  for j in range(W+1) :
    if dptemp[j] > 0 and j+H[i][0] <= W:
      dp[j+H[i][0]] = max(dptemp[j+H[i][0]], dptemp[j] + H[i][1])
    
  dp[H[i][0]] = max(dptemp[H[i][0]], H[i][1])
  #print (dp)      
#print (dp)

print (max(dp))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
goods = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i, item in enumerate(goods):
    i += 1
    for w in range(1, W+1):
        if w < item[0]:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-item[0]] + item[1])

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
w = [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 j in range(W + 1):
        if j - w[i][0] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i][0]] + w[i][1])

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def main():
    a = [int(x) for x in input().split()]
    n, W = a[0], a[1]
    dp = [0 for _ in range(W + 1)]
    a = [[int(x) for x in input().split()] for _ in range(n)]
    for item in range(n):
        weight, value = a[item][0], a[item][1]
        for weight_used in range(W - weight, -1, -1):
            dp[weight + weight_used] = max(dp[weight + weight_used], dp[weight_used] + value)
    a = 0
    for i in range(W+1):
        a = max(a, dp[i])
    print(a)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    a = [int(x) for x in input().split()]
    n, W = a[0], a[1]
    dp = [0] * (W + 1)
    for item in range(n):
        a = [int(x) for x in input().split()]
        weight, value = a[0], a[1]
        for weight_used in range(W - weight, -1, -1):
            dp[weight + weight_used] = max(dp[weight + weight_used], dp[weight_used] + value)
    a = 0
    for i in range(W+1):
        a = max(a, dp[i])
    print(a)


main()

Submission status: Time Limit Exceeded

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

inf=float("inf")
dp=[[-inf for i in range(W+1)] for j in range(N+1)]
for i in range(W+1): dp[0][i]=0

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


print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
W = []
V = []
for _ in range(n):
    s, t = map(int, input().split())
    W.append(s)
    V.append(t)

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

for i in range(n):
    for j in range(w+1):
        #対象となる重さjよりも、見ているものの重さが小さい時
        if W[i] <= j:
            Dp[i+1][j] = max(Dp[i][j], Dp[i][j-W[i]]+V[i])
        else:
            Dp[i+1][j] = Dp[i][j]

ans = Dp[-1][-1]
print(ans)

Submission status: Time Limit Exceeded

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

    dp = [0 for i in range(W+1)]
    for w, v in WV:
        for j in range(W, w-1, -1):
            dp[j] = max(dp[j],dp[j-w] + v)
            
    print(dp[-1])
main()

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
lwv=[]
for i in range(N):
    lwv.append(list(map(int,input().split())))
ldp=[[0 for j in range(W+1)] for i in range(N)]
for j in range(W+1):
    if lwv[0][0]<=j:
        ldp[0][j]=lwv[0][1]
for i in range(1,N):
    for j in range(W+1):
        if j-lwv[i][0]>=0:
            ldp[i][j]=max(ldp[i-1][j],ldp[i-1][j-lwv[i][0]]+lwv[i][1])
        else:
            ldp[i][j]=ldp[i-1][j]
print(ldp[N-1][W])

Submission status: Time Limit Exceeded

Solution code:
def main():
    
    N,W = map(int,input().split())
    wa = []
    va = []
    for i in range(N):
        w,v = map(int,input().split())
        wa.append(w)
        va.append(v)
    dp = [[0 for i in range(W+1)] for j in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            if j-wa[i] >= 0:
                dp[i+1][j] = max(dp[i][j],dp[i][j-wa[i]]+va[i])
            else:
                dp[i+1][j] = dp[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    
    N,W = map(int,input().split())
    array = []
    for i in range(N):
        wv = list(map(int,input().split()))
        array.append(wv)
    dp = [[0 for i in range(W+1)] for j in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            if j-array[i][0] >= 0:
                dp[i+1][j] = max(dp[i][j],dp[i][j-array[i][0]]+array[i][1])
            else:
                dp[i+1][j] = dp[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
array = []
for i in range(N):
    wv = list(map(int,input().split()))
    array.append(wv)
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j-array[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j],dp[i][j-array[i][0]]+array[i][1])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[-1][-1])