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:
def knapSack(W, wt, val, n):
    if W == 0 or n == 0:
        return 0
    elif wt[n-1] > W:
        return knapSack(W, wt, val, n-1)
    else:
        return max(val[n-1] + knapSack(W - wt[n-1], wt, val, n-1),
                   knapSack(W, wt, val, n-1))



N, W = [int(x) for x in input().split()]
wt = []
v = []
for i in range(N):
    k, q = [int(x) for x in input().split()]
    wt.append(k)
    v.append(q)

print(knapSack(W, wt, v, N))

Submission status: Time Limit Exceeded

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

dp=[[0 for i in range(W+10)] for j in range(N+10)]

for i in range(N):
    for j in range(W+1):
        if(j-w[i]>=0):
            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:
def main():
    n,w = map(int,input().split())
    dp = [[0]*(w+1) for j in range(n+1)] # DPテーブルの作成
    v = []
    W = []
    for i in range(n):
        w_,v_ = map(int,input().split())
        v.append(v_)
        W.append(w_)
    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])
main()

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
dp = [[0]*(w+1) for j in range(n+1)] # DPテーブルの作成
v = []
W = []
for i in range(n):
    w_,v_ = map(int,input().split())
    v.append(v_)
    W.append(w_)
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 main():
    n, maxW, weight, value = getInputs()

    maxCount = {}
    for w in range(n):
        if str(w) in maxCount:
            maxCount[str(w)] += 1
        else:
            maxCount[str(w)] = 1

    accumulatedValue = [0] * (maxW + 1)
    possible = [False] * (maxW + 1)
    possible[0] = True

    used = []
    for i in range(maxW + 1):
        used.append({})

    for x in range(min(weight), maxW + 1):
        for w in range(n):
            if (x - weight[w] >= 0) and possible[x - weight[w]] \
                and (str(w) not in used[x - weight[w]] or used[x - weight[w]][str(w)] < maxCount[str(w)]):

                if accumulatedValue[x - weight[w]] + value[w] > accumulatedValue[x]:
                    accumulatedValue[x] = accumulatedValue[x - weight[w]] + value[w]
                    used[x] = used[x - weight[w]].copy()
                    if str(w) in used[x]:
                        used[x][str(w)] += 1
                    else:
                        used[x][str(w)] = 1

                    possible[x] = True

    print(max(accumulatedValue))

def getInputs():
    n, maxW = map(lambda x: int(x), input().split())

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

    return n, maxW, weight, value

main()

Submission status: Time Limit Exceeded

Solution code:
f = input().split()
n = int(f[0])
w = int(f[1])

arr = []
for i in range(n):
    a = input().split()
    a = [ int(a[j]) for j in range(2)]
    arr.append(a)
memo=[0 for i in range(w+1)]
memo1=[0 for i in range(w+1)]

for i in range(n):
    for j in range(arr[i][0],w+1):
        memo1[j] = max(memo[j-arr[i][0]] + arr[i][1], memo[j])
    memo = [memo1[j] for j in range(w+1)]
print(memo[w])

Submission status: Time Limit Exceeded

Solution code:
f = input().split()
n = int(f[0])
w = int(f[1])

arr = []
for i in range(n):
    a = input().split()
    a = [ int(a[j]) for j in range(2)]
    arr.append(a)
memo=[0 for i in range(w+1)]
memo1=[0 for i in range(w+1)]

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

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

    dp = [defaultdict(int)]
    dp[0][0] = 0
    for i in range(N):
        w, v = map(int, input().split())
        keys = list(dp[i].keys())
        new_dp = defaultdict(int)
        for key in keys:
            new_dp[key] = max([new_dp[key], dp[i][key]])
            new_w = key + w
            if new_w <= W:
                new_dp[new_w] = max([new_dp[new_w], dp[i][key] + v])
        dp.append(new_dp)
    print(max(dp[N].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)]

dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1, N+1):
    for sum_w in range(W+1):
        weight = sum_w - wv[i-1][0]
        if weight < 0:
            dp[i][sum_w] = max([dp[i][sum_w], dp[i-1][sum_w]])
        else:
            dp[i][sum_w] = max([dp[i][sum_w], dp[i-1][sum_w], dp[i-1][weight]+wv[i-1][1]])
print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
N, W = list(map(int, input().split()))
w, v = [None] * N, [None] * N
for i in range(N):
    w[i], v[i] = list(map(int, input().split()))


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

ans = max(dp[N])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = (int(x) for x in input().split())
dp = [0] * (W+1) # Maximum value of items we can carry at weight
for _ in range(N):
  w, v = (int(x) for x in input().split())
  for cur in range(W, w-1, -1):
    dp[cur] = max(dp[cur-w]+v, dp[cur])

print(dp[W])

Submission status: Time Limit Exceeded

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

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

def solve(idx, weight, val):
    if weight > W:
        return -1
    if idx == N:
        return val

    # select
    v1 = solve(idx + 1, weight + w[idx], val + v[idx])

    # not select
    v2 = solve(idx + 1, weight, val)

    return max(v1, v2)

print(solve(0, 0, 0))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def recursion(li,i,n,w,dp):
    if i==n or w==0:
        return 0
    if li[i][0]>w:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        return x
    else:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        if dp[i+1][w-li[i][0]]==-1:
            y=recursion(li,i+1,n,w-li[i][0],dp)
            dp[i+1][w-li[i][0]]=y
        else:
            y=dp[i+1][w-li[i][0]]            
        return max(li[i][1]+y,x)

n,w=[int(x) for x in input().split()]
li=[]
for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
dp=[[-1 for j in range(w+1)] for i in range(n+1)]
print(recursion(li,0,n,w,dp))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, gettrace
 
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()
 
def main():
  
  n,w=map(int,input().split())
  li=[]
  for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
  dp=[[[-1,-1] for j in range(w+1)] for i in range(n)]
  dp[n-1][0]=[li[n-1][1],li[n-1][1]]
  for i in range(n-1,-1,-1):
    for j in range(w,-1,-1):
      if j==0:
        dp[i][j]=li[i][1],li[i][1]
      if i==(n-1):
        if li[i][0]<=j:
          dp[i][j]=li[i][1],li[i][1]
        else:
          dp[i][j]=0,0
      else:
        mx=li[i][1]
        for k in range(i+1,n):
          if (j-li[i][0])>=li[k][0]:
            val=dp[k][j-li[i][0]]
            mx=max(mx,val[0]+li[i][1])
          val=dp[i+1][j]
          overall=max(mx,val[1])
          dp[i][j]=[mx,overall]
          
  print(dp[0][w][1])
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
li=[]
for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
dp=[[[-1,-1] for j in range(w+1)] for i in range(n)]
dp[n-1][0]=[li[n-1][1],li[n-1][1]]
for i in range(n-1,-1,-1):
    for j in range(w,-1,-1):
        if j==0:
            dp[i][j]=li[i][1],li[i][1]
        if i==(n-1):
            if li[i][0]<=j:
                dp[i][j]=li[i][1],li[i][1]
            else:
                dp[i][j]=0,0
        else:
            mx=li[i][1]
            for k in range(i+1,n):
                if (j-li[i][0])>=li[k][0]:
                    val=dp[k][j-li[i][0]]
                    mx=max(mx,val[0]+li[i][1])
            val=dp[i+1][j]
            overall=max(mx,val[1])
            dp[i][j]=[mx,overall]
print(dp[0][w][1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def recur(li,i,n,w,dp):
    if i==(n-1):
        if w<=li[i][0]:
            return li[i][1],li[i][1]
        else:
            return 0,0
    if w==0:
        return li[i][1],li[i][1]
    mx=li[i][1]
    for j in range(i+1,n):
        if (w-li[i][0])>=li[j][0]:
            if dp[j][w-li[i][0]]==[-1,-1]:
                val=recur(li,j,n,w-li[i][0],dp)
                dp[j][w-li[i][0]]=val
            else:
                val=dp[j][w-li[i][0]]
            mx=max(mx,val[0]+li[i][1])
    if dp[i+1][w]==[-1,-1]:
        val=recur(li,i+1,n,w,dp)
        dp[i+1][w]=val
    else:
        val=dp[i+1][w]
    overall=max(mx,val[1])
    #print(mx,overall)
    return mx,overall

n,w=map(int,input().split())
li=[]
for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
dp=[[[-1,-1] for j in range(w+1)] for i in range(n)]
print(recur(li,0,n,w,dp)[1])

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

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

Submission status: Time Limit Exceeded

Solution code:

def knapsack01rec(n, W, weights, values, dp, i, j):
    if i == 0 or j <= 0:
        return 0

    if (i,j) in dp:
        return dp[i,j]

    if weights[i-1] > j:
        dp[i,j] = knapsack01rec(n, W, weights, values, dp, i-1, j)
    else:
        dp[i,j] = max(
            knapsack01rec(n, W, weights, values, dp, i-1, j),
            knapsack01rec(n, W, weights, values, dp, i-1, j-weights[i-1]) + values[i-1])

    return dp[i,j]


n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

res = knapsack01rec(n, W, weights, values, {}, n, W)
print(res)

Submission status: Time Limit Exceeded

Solution code:

def knapsack01rec(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    # print(i, j)
    if i == 0 or j <= 0:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]

    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = knapsack01rec(n, W, weights, values, dp, i-1, j)
    else:
        dp[i][j] = max(
            knapsack01rec(n, W, weights, values, dp, i-1, j),
            knapsack01rec(n, W, weights, values, dp, i-1, j-weights[i-1]) + values[i-1])

    return dp[i][j]


n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
print(res)

Submission status: Time Limit Exceeded

Solution code:
def solve(dp, l, w, i):
    if i < 0:
        return 0
    if w in dp[i]:
        return dp[i][w]
    ret = solve(dp, l, w, i-1)
    if l[i][0] <= w:
        ret = max(ret, solve(dp, l, w-l[i][0], i-1) + l[i][1])
    dp[i][w] = ret
    return ret

n, w = (int(x) for x in input().split())
l = []
for _ in range(n):
    l.append([int(x) for x in input().split()])
dp = []
while len(dp) < len(l):
    dp.append(dict())
print(solve(dp, l, w, len(l)-1))

Submission status: Time Limit Exceeded

Solution code:
def solve(dp, l, w, i):
    if i < 0:
        return 0
    if (i, w) in dp:
        return dp[(i, w)]
    ret = solve(dp, l, w, i-1)
    if l[i][0] <= w:
        ret = max(ret, solve(dp, l, w-l[i][0], i-1) + l[i][1])
    dp[(i, w)] = ret
    return ret

n, w = (int(x) for x in input().split())
l = []
for _ in range(n):
    l.append([int(x) for x in input().split()])
dp = dict()
print(solve(dp, l, w, len(l)-1))

Submission status: Time Limit Exceeded

Solution code:
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

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

def knapsack01rec(i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]

    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = knapsack01rec(i-1, j)
    else:
        dp[i][j] = max(
            knapsack01rec(i-1, j),
            knapsack01rec(i-1, j-weights[i-1]) + values[i-1])
    return dp[i][j]

res = knapsack01rec(n, W)
print(res)

Submission status: Time Limit Exceeded

Solution code:
def knapsack01rec(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]

    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = knapsack01rec(n, W, weights, values, dp, i-1, j)
    else:
        dp[i][j] = max(
            knapsack01rec(n, W, weights, values, dp, i-1, j),
            knapsack01rec(n, W, weights, values, dp, i-1, j-weights[i-1]) + values[i-1])
    return dp[i][j]

n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01rec(n, W, weights, values, dp, n, W)

print(res)

Submission status: Time Limit Exceeded

Solution code:
def knapsack01rec(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0
    
    if dp[i][j] != -1:
        return dp[i][j]
    
    # start with first item
    if dp[i-1][j] == -1:
        dp[i-1][j] = knapsack01rec(n, W, weights, values, dp, i-1, j)
    
    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = dp[i-1][j]
    else:
        if dp[i-1][j-weights[i-1]] == -1:
            dp[i-1][j-weights[i-1]] = knapsack01rec(n, W, weights, values, dp, i-1, j-weights[i-1])
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
        
    return dp[i][j]

n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]
dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01rec(n, W, weights, values, dp, n, W)
print(res)

Submission status: Time Limit Exceeded

Solution code:

def knapsack01rec(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0
    
    if dp[i][j] != -1:
        return dp[i][j]
    
    # start with first item
    if dp[i-1][j] == -1:
        dp[i-1][j] = knapsack01rec(n, W, weights, values, dp, i-1, j)
    
    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = dp[i-1][j]
    else:
        if dp[i-1][j-weights[i-1]] == -1:
            dp[i-1][j-weights[i-1]] = knapsack01rec(n, W, weights, values, dp, i-1, j-weights[i-1])
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
        
    return dp[i][j]

def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: # if knapsack cannot fit item i
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: # knapsack can fit item i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
# dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
# res = knapsack01iter(n, W, weights, values, dp)
# print(dp)
print(res)

Submission status: Time Limit Exceeded

Solution code:
def knapsack01(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0
    
    # start with first item
    if dp[i-1][j] == -1:
        dp[i-1][j] = knapsack01(n, W, weights, values, dp, i-1, j)
    
    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = dp[i-1][j]
    else:
        if dp[i-1][j-weights[i-1]] == -1:
            dp[i-1][j-weights[i-1]] = knapsack01(n, W, weights, values, dp, i-1, j-weights[i-1])
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
        
    return dp[i][j]
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01(n, W, weights, values, dp, n, W)
# print(dp)
print(res)

Submission status: Time Limit Exceeded

Solution code:
def repeatableKnapsack(n, W, weights, values):
    dp = [0 for _ in range(W+1)]
    dp[0] = 0
    # print(weights, values)
    for i in range(1,W+1):
        for j in range(n):
            if weights[j] <= i:
                dp[i] = max(dp[i], values[j]+dp[i-weights[j]])
    # print(dp)
    print(dp[-1])
    
def knapsack01(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0
    
    # start with first item
    if dp[i-1][j] == -1:
        dp[i-1][j] = knapsack01(n, W, weights, values, dp, i-1, j)
    
    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = dp[i-1][j]
    else:
        if dp[i-1][j-weights[i-1]] == -1:
            dp[i-1][j-weights[i-1]] = knapsack01(n, W, weights, values, dp, i-1, j-weights[i-1])
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
        
    return dp[i][j]
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01(n, W, weights, values, dp, n, W)
# print(dp)
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import math
from collections import Counter
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

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

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

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

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


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

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
##########################################################
# for i in range(int(input())):
# arr = list(map(int, input().split()))
# a,b= map(int, input().split())
import bisect
#for i in range(int(input())):
def knap(i,c,w,v):
    if c==0 or i==0:
        return 0
    if w[i-1]<=c:
        return max(v[i-1]+knap(i-1,c-w[i-1],w,v),knap(i-1,c,w,v))
    else:
        return knap(i-1,c,w,v,)
n,c = map(int, input().split())
w=[]
v=[]
for i in range(n):
    a,b= map(int, input().split())
    w.append(a)
    v.append(b)
print(knap(n,c,w,v))

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
v = [0]*n
for i in range(n):
    v[i] = list(map(int,input().split()))
dp =  [[0 for j in range(w+1)] for i in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j - v[i][0] >= 0:
            if dp[i][j-v[i][0]] + v[i][1] > dp[i][j]:
                dp[i+1][j] = dp[i][j-v[i][0]] + v[i][1]
        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
import math
import numpy as np
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    N ,W = I2()
    w = [0]*N
    v = [0]*W
    dp = np.zeros([N+1,W+1],dtype = "int64")
    for i in range(N):
        a,b = I2()
        w[i] = a
        v[i] = b
    for i in range(N):
        for j in range(0,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)
    print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:

import os
import sys
from io import BytesIO, IOBase

def knapsack(wt,price,n,c,dp):
    if n<0 or c==0:
        return 0
    if dp[n][c]!=-1:
        return dp[n][c]
    inc=exc=0
    if c>=wt[n]:
        inc=price[n]+knapsack(wt,price,n-1,c-wt[n],dp)
    exc=0+knapsack(wt,price,n-1,c,dp)
    dp[n][c]=max(inc,exc)
    return max(inc,exc)

def main():
    n,c=map(int,input().split())
    wt=[]
    price=[]
    for _ in range(n):
        w,v=map(int,input().split())
        wt.append(w)
        price.append(v)
    dp=[[-1 for x in range(c+1)] for y in range(n+1)]
    print(knapsack(wt,price,n-1,c,dp))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

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

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

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

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


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


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

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def knapsack(wt,price,n,c,dp):
    if n<0 or c==0:
        return 0
    if dp[n][c]!=-1:
        return dp[n][c]
    inc=exc=0
    if c>=wt[n]:
        inc=price[n]+knapsack(wt,price,n-1,c-wt[n],dp)
    exc=0+knapsack(wt,price,n-1,c,dp)
    dp[n][c]=max(inc,exc)
    return max(inc,exc)

n,c=map(int,input().split())
wt=[]
price=[]
for _ in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    price.append(v)
dp=[[-1 for x in range(c+1)] for y in range(n+1)]
print(knapsack(wt,price,n-1,c,dp))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:

n, w = map(int, input().split())
dp = [[0 for x in range(w + 1)] for y in range(n + 1)]

weights = list()
profits = list()

for i in range(n):
    W, P = map(int, input().split())
    weights.append(W)
    profits.append(P)

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

print(dp[n][w])

Submission status: Time Limit Exceeded

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

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

for i in range(N):
  for j in range(W+1):
    if j>=a[i][0] and i==0: 
        dp[i][j]=a[i][1]
    elif  j>=a[i][0]: 
      if dp[i-1][j] < dp[i-1][j-a[i][0]] +a[i][1]:
        dp[i][j]=dp[i-1][j-a[i][0]] +a[i][1]
      else:
        dp[i][j]=dp[i-1][j]
    else:
      dp[i][j]=dp[i-1][j]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def solve():
    matrix = [[0]*(w+1) for _ in range(n)]
    for i in range(n):
        for j in range(1, w+1):
            if i >= 1 and j-dp[i][0] >= 0:
                matrix[i][j] = max(matrix[i-1][j], dp[i][1]+matrix[i-1][j-dp[i][0]])
            elif i < 1 and j-dp[i][0] >= 0:
                matrix[i][j] = dp[i][1]
            else:
                matrix[i][j] = matrix[i-1][j]
    return matrix[n-1][w]


if __name__ == '__main__':
    n, w = map(int, input().split())
    dp = []
    for i in range(n):
        dp.append(list(map(int,input().split())))
    print(solve())

Submission status: Time Limit Exceeded

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

for weight in range(1,W+1):
    for good in range(1,N+1):
        if weight-wv[good][0] >= 0:
            dp[good][weight] = max(dp[good-1][weight-wv[good][0]]+wv[good][1], dp[good-1][weight])
        else:
            dp[good][weight] = dp[good-1][weight]

print(dp[N][W])