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())
box = []
for i in range(n):
  W,V = map(int,input().split())
  box.append([W,V])
dp = [[0 for i in range(w+1)] for j in range(n+1)]

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

Submission status: Time Limit Exceeded

Solution code:
# D Knapsack 1

from collections import deque

n, w = map(int,input().split())
wv_list = deque([[int(x) for x in input().split()] for y in range(n)])

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)

for i in range(n):
    _w,_v = wv_list.popleft()
    for j in range(w+1):
        if j-_w < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-_w]+_v)

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
# D Knapsack 1

n, w = map(int,input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)]

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)

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

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    # n = int(input())
    # 整数複数個
    n, w = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    # N = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    A = [list(map(int, input().split())) for i in range(n)]

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

    for i in range(n):
        for j in reversed(range(i+1)):
            for k in range(w+1):
#                if (Knap[j][k] > 0 or (j == 0 and k ==0)) and k + A[i][0] <= w:
                point = k + A[i][0]
                if point <= w:
                    Knap[j+1][k + A[i][0]] = max((Knap[j+1][point]), (Knap[j][k] + A[i][1]))

    knapmax = 0
    for i in range(n):
        knapmax = max(knapmax, max(Knap[i+1]))
    print(knapmax)

resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    # n = int(input())
    # 整数複数個
    n, w = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    # N = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    A = [list(map(int, input().split())) for i in range(n)]

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

    for i in range(n):
        for j in reversed(range(i+1)):
            for k in range(w+1):
                if (Knap[j][k] > 0 or (j == 0 and k ==0)) and k + A[i][0] <= w:
                    Knap[j+1][k + A[i][0]] = max((Knap[j+1][k + A[i][0]]), (Knap[j][k] + A[i][1]))

    knapmax = 0
    for i in range(n):
        knapmax = max(knapmax, max(Knap[i+1]))
    print(knapmax)

resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W=list(map(int,input().split()))
DP=np.arange((N+1)*(W+1)).reshape(N+1,W+1)
DP=np.zeros_like(DP,dtype=float)
sumv=float(0)
for i in range(1,N+1):
    w,v=list(map(int,input().split()))
    sumv+=v
    for j in range(W+1):
        if j-w>=0:
            DP[i][j]=max(DP[i-1][j],DP[i-1][j-w]+v)
            if DP[i][j]==sumv:
                DP[i][j:]=DP[i][j]
                break
        else:
            DP[i][j]=max(DP[i-1][j],DP[i][j-1])
print(int(DP[-1][-1]))
# for i in DP:
#     print(i)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:



n,w = list(map(int, input().split()))
weights,vals = [],[]
best = [0]*(w+1)
for i in range(n):
    a,b = list(map(int, input().split()))

    for weight in range(w-a, -1,-1):
        best[weight+a] = max(best[weight+a], best[weight]+b)

print(max(best))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N
for i in range(N):
    weights[i],profits[i] = map(int,input().split())

@lru_cache(None)
def knapsack_recursive(capacity, currentIndex):
    if capacity <= 0 or currentIndex >= len(profits): return 0
    profit = 0
    if weights[currentIndex] <= capacity:
        profit = profits[currentIndex] + knapsack_recursive(capacity - weights[currentIndex], currentIndex + 1)
    tmp = knapsack_recursive(capacity, currentIndex + 1)
    if tmp > profit:
        profit = tmp  
    return profit
  
def main():
    res = knapsack_recursive(W, 0)
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
N,W=map(int,input().split())
weights0,profits0 = [0]*N, [0]*N
for i in range(N):
    weights0[i],profits0[i] = map(int,input().split())
weights0 = tuple(weights0)
profits0 = tuple(profits0)
 
@lru_cache(maxsize=100)
def knapsack_recursive(weights, profits, capacity, currentIndex):
    if capacity <= 0 or currentIndex >= len(profits): return 0
    profit = 0
    if weights[currentIndex] <= capacity:
        profit = profits[currentIndex] + knapsack_recursive(weights, profits, capacity - weights[currentIndex], currentIndex + 1)
    tmp = knapsack_recursive(weights, profits, capacity, currentIndex + 1)
    if tmp > profit:
        profit = tmp  
    return profit
  
def main():
    res = knapsack_recursive(weights0, profits0, W, 0)
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
N,W=map(int,input().split())
weights0,profits0 = [0]*N, [0]*N
for i in range(N):
    weights0[i],profits0[i] = map(int,input().split())
weights0 = tuple(weights0)
profits0 = tuple(profits0)

@lru_cache(maxsize=1024)
def knapsack_recursive(weights, profits, capacity, currentIndex):
    if capacity <= 0 or currentIndex >= len(profits): return 0
    profit = 0
    if weights[currentIndex] <= capacity:
        profit = profits[currentIndex] + knapsack_recursive(weights, profits, capacity - weights[currentIndex], currentIndex + 1)
    tmp = knapsack_recursive(weights, profits, capacity, currentIndex + 1)
    if tmp > profit:
        profit = tmp  
    return profit
  
def main():
    res = knapsack_recursive(weights0, profits0, W, 0)
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
N,W=map(int,input().split())
weights0,profits0 = [0]*N, [0]*N
for i in range(N):
    weights0[i],profits0[i] = map(int,input().split())
weights0 = tuple(weights0)
profits0 = tuple(profits0)

@lru_cache(None)
def knapsack_recursive(weights, profits, capacity, currentIndex):
    if capacity <= 0 or currentIndex >= len(profits): return 0
    profit = 0
    if weights[currentIndex] <= capacity:
        profit = profits[currentIndex] + knapsack_recursive(weights, profits, capacity - weights[currentIndex], currentIndex + 1)
    tmp = knapsack_recursive(weights, profits, capacity, currentIndex + 1)
    if tmp > profit:
        profit = tmp  
    return profit
  
def main():
    res = knapsack_recursive(weights0, profits0, W, 0)
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
N,W=map(int,input().split())

@lru_cache(None)
def knapsack_recursive(capacity, currentIndex):
    if capacity <= 0 or currentIndex >= len(profits): return 0

    profit = 0
    if weights[currentIndex] <= capacity:
        profit = profits[currentIndex] + knapsack_recursive(capacity - weights[currentIndex], currentIndex + 1)
    tmp = knapsack_recursive(capacity, currentIndex + 1)
    if tmp > profit:
        profit = tmp  
    return profit
  
def main():

    res = knapsack_recursive(W, 0)

    print(res)
if __name__ == "__main__":
    weights,profits = [0]*N, [0]*N
    for i in range(N):
        weights[i],profits[i] = map(int,input().split())
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N
for i in range(N):
    weights[i],profits[i] = map(int,input().split())
@lru_cache(None)
def knapsack_recursive(capacity, currentIndex):


    if capacity <= 0 or currentIndex >= len(profits): return 0

    profit = 0
    if weights[currentIndex] <= capacity:
        profit = profits[currentIndex] + knapsack_recursive(capacity - weights[currentIndex], currentIndex + 1)
    tmp = knapsack_recursive(capacity, currentIndex + 1)
    if tmp > profit:
        profit = tmp  
    return profit
  
def main():

    res = knapsack_recursive(W, 0)

    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    dp = [0]*(W + 1)
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            dp[c] = profits + dp[c - weights] if profits + dp[c - weights] > dp[c] else dp[c]
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    dp = [0]*(W + 1)
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            dp[c] = max(dp[c], profits + dp[c - weights])
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    dp = [0]*(W + 1)
    weights, profits = [0]*(N+1), [0]*(N+1)
    for i in range(0, N):
        weights[i],profits[i] = map(int,input().split())
    

    for i in range(0, N):
        for c in range(capacity, weights[i]-1, -1):
            dp[c] = max(dp[c], profits[i] + dp[c - weights[i]])
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

def solve_knapsack(capacity):
    # basic checks
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            dp[c] = max(dp[c], profits + dp[c - weights])
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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


N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N
def solve_knapsack(capacity):
    # basic checks
    n = len(profits)
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, n):
        weights[i],profits[i] = map(int,input().split())
        for c in range(capacity, weights[i]-1, -1):
            tmp = profits[i] + dp[c - weights[i]]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N
def solve_knapsack(capacity):
    # basic checks
    n = len(profits)
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, n):
        weights[i],profits[i] = map(int,input().split())
        for c in range(capacity, weights[i]-1, -1):
            tmp = profits[i] + dp[c - weights[i]]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N
def solve_knapsack(capacity):
    # basic checks
    n = len(profits)
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, n):
        weights[i],profits[i] = map(int,input().split())
        for c in range(capacity, weights[i]-1, -1):
            dp[c] = max(profits[i] + dp[c - weights[i]], dp[c])
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N
def solve_knapsack(capacity):
    # basic checks
    n = len(profits)
 
    dp = [0 for x in range(capacity+1)]
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, n):
        weights[i],profits[i] = map(int,input().split())
        for c in range(capacity, weights[i]-1, -1):
            if weights[i] <= c:
                dp[c] = max(profits[i] + dp[c - weights[i]], dp[c])
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N
def solve_knapsack(profits, weights, capacity):
    # basic checks
    n = len(profits)
 
    dp = [0 for x in range(capacity+1)]
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    dp[0] = 0
    for c in range(0, capacity+1):
        if weights[0] <= c: dp[c] = profits[0]
    for i in range(1, n):
        for c in range(capacity, weights[i], -1):
            if weights[i] <= c:
                dp[c] = max(profits[i] + dp[c - weights[i]], dp[c])
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    for i in range(N):
        weights[i],profits[i] = map(int,input().split())
    res = solve_knapsack(profits, weights, W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N
def solve_knapsack(profits, weights, capacity):
    # basic checks
    n = len(profits)
 
    dp = [[0 for x in range(capacity+1)] for y in range(n)]
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    for i in range(0, n):
        dp[i][0] = 0
    for c in range(0, capacity+1):
        if weights[0] <= c: dp[0][c] = profits[0]
    for i in range(1, n):
        for c in range(1, capacity+1):
            if weights[i] <= c:
                dp[i][c] = max(profits[i] + dp[i - 1][c - weights[i]], dp[i - 1][c])
            else: dp[i][c]  = dp[i - 1][c]
 
    # maximum profit will be at the bottom-right corner.
    return dp[n - 1][capacity]
  
def main():
 
    for i in range(N):
        weights[i],profits[i] = map(int,input().split())
    res = solve_knapsack(profits, weights, W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N

@lru_cache(None)
def knapsack_recursive(capacity, currentIndex):
 
  # base checks
    if capacity <= 0 or currentIndex >= len(profits): return 0

    profit1 = 0
    if weights[currentIndex] <= capacity:
        profit1 = profits[currentIndex] + knapsack_recursive(capacity - weights[currentIndex], currentIndex + 1)
    profit2 = knapsack_recursive(capacity, currentIndex + 1)
    return max(profit1, profit2)
  
def main():

    for i in range(N):
        weights[i],profits[i] = map(int,input().split())
    res = knapsack_recursive(W, 0)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N

@lru_cache(None)
def knapsack_recursive(capacity, currentIndex):
 
  # base checks
    if capacity <= 0 or currentIndex >= len(profits): return 0

    profit1 = 0
    if weights[currentIndex] <= capacity:
        profit1 = profits[currentIndex] + knapsack_recursive(capacity - weights[currentIndex], currentIndex + 1)
 
  # recursive call after excluding the element at the currentIndex
    profit2 = knapsack_recursive(capacity, currentIndex + 1)
 
    return max(profit1, profit2)
  
def main():

    for i in range(N):
        weights[i],profits[i] = map(int,input().split())
    res = knapsack_recursive(W, 0)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
def solve_knapsack(profits, weights, capacity):
  # create a two dimensional array for Memoization, each element is initialized to '-1'
	dp = [[-1 for x in range(capacity+1)] for y in range(len(profits))]
	return knapsack_recursive(dp, profits, weights, capacity, 0)
 
 
def knapsack_recursive(dp, profits, weights, capacity, currentIndex):
 
  # base checks
    if capacity <= 0 or currentIndex >= len(profits): return 0
 
  # if we have already solved a similar problem, return the result from memory
    if dp[currentIndex][capacity] != -1: return dp[currentIndex][capacity]
 
  # recursive call after choosing the element at the currentIndex
  # if the weight of the element at currentIndex exceeds the capacity, we
  # shouldn't process this
    profit1 = 0
    if weights[currentIndex] <= capacity:
        profit1 = profits[currentIndex] + knapsack_recursive(dp, profits, weights, capacity - weights[currentIndex], currentIndex + 1)
 
  # recursive call after excluding the element at the currentIndex
    profit2 = knapsack_recursive(dp, profits, weights, capacity, currentIndex + 1)
 
    dp[currentIndex][capacity] = max(profit1, profit2)
    return dp[currentIndex][capacity]
  
def main():
    N,W=map(int,input().split())
    w,v = [0]*N, [0]*N
    for i in range(N):
        w[i],v[i] = map(int,input().split())
    res = solve_knapsack(v, w, W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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


def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))


def get_array(): return list(map(int, sys.stdin.readline().strip().split()))


[n, W] = get_ints()

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

val = []
weights = []
for i in range(n):
    [w, v] = get_ints()
    val.append(v)
    weights.append(w)

for i in range(1, n + 1):
    for j in range(1, W + 1):

        if j - weights[i - 1] >= 0:
            dp[i][j] = max(val[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j])

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

sys.stdout.write(str(dp[n][W]))

Submission status: Time Limit Exceeded

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


def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))


def get_array(): return list(map(int, sys.stdin.readline().strip().split()))


def ks(val, w, W, n, dp):

    if n == 0:
        return 0

    if (n, W) in dp:
        return dp[(n, W)]

    if w[n - 1] > W:
        return ks(val, w, W, n - 1, dp)

    dp[(n, W)] = max(ks(val, w, W - w[n - 1], n - 1, dp) + val[n - 1], ks(val, w, W, n - 1, dp))
    return dp[(n, W)]


[n, W] = get_ints()
val = []
weights = []
for i in range(n):
    [w, v] = get_ints()
    val.append(v)
    weights.append(w)

dp = {}
sys.stdout.write(str(ks(val, weights, W, n, dp)))

Submission status: Time Limit Exceeded

Solution code:
import sys


def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))


def get_array(): return list(map(int, sys.stdin.readline().strip().split()))

def ks(val, w, W, n, dp):

    if n == 0:
        return 0

    if (n, W) in dp:
        return dp[(n, W)]

    if w[n - 1] > W:
        return ks(val, w, W, n - 1, dp)

    dp[(n, W)] = max(ks(val, w, W - w[n - 1], n - 1, dp) + val[n - 1], ks(val, w, W, n - 1, dp))
    return dp[(n, W)]


n, W = list(map(int, sys.stdin.readline().split()))
val = []
weights = []
for i in range(n):
    w, v = list(map(int, sys.stdin.readline().strip().split()))
    val.append(v)
    weights.append(w)

dp = {}

sys.stdout.write(str(ks(val, weights, W, n, dp)))

Submission status: Time Limit Exceeded

Solution code:
import sys


def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))


def get_array(): return list(map(int, sys.stdin.readline().strip().split()))


def ks(val, w, W, n):


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

    for i in range(1, n + 1):
        for j in range(1, W + 1):

            if j - w[i - 1] >= 0:
                dp[i][j] = max(val[i - 1] + dp[i - 1][j - w[i - 1]], dp[i - 1][j])

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

    return dp[n][W]


# n, k = get_ints()
# arr = get_array()

# sys.stdout.write(str(frog_1(arr, n, k)))

n, W = list(map(int, sys.stdin.readline().split()))
val = []
weights = []
for i in range(n):
    w, v = list(map(int, sys.stdin.readline().strip().split()))
    val.append(v)
    weights.append(w)

sys.stdout.write(str(ks(val, weights, W, n)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def knapsack(N, C, weights, values):
    dp = [[0 for _ in range(N + 1)] for _ in range(C + 1)]
    for i in range(1, C + 1):
        for j in range(1, N + 1):
            if weights[j - 1] <= i:
                dp[i][j] = max(dp[i][j - 1], values[j - 1] + dp[i - weights[j - 1]][j - 1])
            else:
                dp[i][j] = dp[i][j - 1]
    return dp[C][N]


if __name__ == '__main__':
    n, c = list(map(int, input().split()))
    weights = [0] * n
    values = [0] * n
    for i in range(n):
        weights[i], values[i] = map(int, input().split())
    print(knapsack(n, c, weights, values))

Submission status: Time Limit Exceeded

Solution code:
# itne me hi thakk gaye?
n, W  = map(int, input().split())
dp = [[0 for i in range(W+1)] for j in range(n+1)]
w, val = [], []
for i in range(n):
	a, b = map(int, input().split())
	w.append(a)
	val.append(b)
for i in range(n+1):
	for j in range(W+1):
		if(i == 0 or j == 0):
			dp[i][j] = 0
		elif w[i-1] > j:
			dp[i][j] = dp[i-1][j]
		else:
			dp[i][j] = max(dp[i-1][j], val[i-1] + dp[i-1][j-w[i-1]])
print(dp[-1][-1])

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,W = map(int, input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int, input().split())
    # dp[i][w] := 容量をwとして荷物0~iの中から荷物を選んだ時の価値の最大値
    # 初期値dp[0][W] = 0の価値(もし0の重さがMAXを超えるなら選べない)
    dp = [[0]*(W+1) for i in range(N)]
    for x in range(W+1):
        dp[0][x] = 0 if w[0]>x else v[0]
    for i in range(N-1):
        for j in range(W+1):
            if w[i+1]<=j:
                # i+1番目を選ぶ
                dp[i+1][j] = max(dp[i+1][j], (dp[i][j-w[i+1]])+v[i+1])
            # i+1番目を選ばない
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    print(dp[-1][W])

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
num = list(map(int, input().split()))
n, tw = num[0], num[1]

w = [0]
v = [0]

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

if sum(w) < tw:
    tw = sum(w)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def recur(dp, C, i, values, weights):
    if C <= 0 or i < 0:
        return 0
    if dp[i][C] != -1:
        return dp[i][C]
    if weights[i] > C:
        dp[i][C] = recur(dp, C, i-1, values, weights)
    else:
        dp[i][C] = max(
            recur(dp, C, i-1, values, weights),
            values[i] + recur(dp, C-weights[i], i-1, values, weights)
        )
    return dp[i][C]
    

def solve():
    N, W = map(int, input().split())
    values, weights = [], []
    for i in range(N):
        w, v = map(int, input().split())
        values.append(v)
        weights.append(w)
    dp = [[-1 for i in range(W+1)] for j in range(N)]
    print(recur(dp, W, N-1, values, weights))
solve()

Submission status: Time Limit Exceeded

Solution code:
num = list(map(int, input().split()))
n, tw = num[0], num[1]

w = [0]
v = [0]

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def knapsack(w,val,W,n,t):
    for i in range(1,n+1):
        for j in range(1,W+1):
            if w[i-1]<=j:
                t[i][j]=max(val[i-1]+t[i-1][j-w[i-1]],t[i-1][j])
            else:
                t[i][j]=t[i-1][j]
    return t[n][W]            
n,W=map(int,input().split())                
w=[]
val=[]
t=np.zeros([n+1,W+1],dtype=int)
for i in range(0,n):
    a,b=map(int,input().split())
    w.append(a)
    val.append(b)
ans=knapsack(w,val,W,n,t)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mips():
  return map(int,input().split())
def chmax(DP,b,weight,number):
    if DP[number+1][weight] < b : 
        DP[number+1][weight] = b
        return True
    return False    
N,W = mips()
Poids = []
Valeur = []
for i in range(N):
    weight,value = mips()
    Poids.append(weight)
    Valeur.append(value)
DP = [[0] * (2*W) for i in range(N+1)]
for i in range(N):
    for sum_p in range(0,W+1):
        if sum_p - Poids[i] >= 0:
            chmax(DP,DP[i][sum_p-Poids[i]] + Valeur[i],sum_p,i)
        chmax(DP,DP[i][sum_p],sum_p,i)
print(DP[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,W= map(int,input().split())
ans=[0 for e in range(W+1)] 
for i in range(N):
 w,v=map(int,input().split())
 for j in range(w,W+1)[::-1]:
  ans[j]=max(ans[j-w]+v,ans[j])
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,W= map(int,input().split())
ans=[[0 for e in range(W+1)] for f in range(N+1)]
for i in range(N):
 w,v=map(int,input().split())
 for k in range(0,w):
  ans[i+1][k]=ans[i][k]
 for j in range(w,W+1):
  ans[i+1][j]=max(ans[i][j-w]+v,ans[i][j])
print(max(ans[N]))