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

Submission status: Time Limit Exceeded

Solution code:
def rec(n,w):
    s=sum(val)
    inf=10**18
    dp=[[inf for i in range(s+1)] for j in range(n+1)]
    for i in range(n+1):
        for j in range(s+1):
            if j==0:
                dp[i][j]=0
            elif i==0:
                continue
            elif val[i-1]>j:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=min(dp[i-1][j-val[i-1]]+wt[i-1],dp[i-1][j])
    m=0
    for i in range(s+1):
        if dp[n][i]<=w:
            m=max(m,i)
    return m
  
n,w=map(int,input().split())
val=[]
wt=[]
for i in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    val.append(b)
print(rec(n,w))

Submission status: Time Limit Exceeded

Solution code:
# your code goes here
# your code goes here
import sys
sample = sys.stdin.read().splitlines()
n, maxW = list(map(int, sample[0].split()))
weights, values = [0], [0]
for x in sample[1:]:
	data = list(map(int, x.split()))
	weights.append(data[0])
	values.append(data[1])

dp = [[0 for _ in range(maxW+1)] for _ in range(len(values))]
#print(dp)
for curr_weight in range(1, len(weights)):
    for j in range(maxW+1):
        if weights[curr_weight] > j:
            dp[curr_weight][j] = dp[curr_weight-1][j]
        else:
            dp[curr_weight][j] = max(dp[curr_weight-1][j], values[curr_weight]+dp[curr_weight-1][j-weights[curr_weight]])

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

#print(dp[len(weights)][maxW])

Submission status: Time Limit Exceeded

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

for i in range(n):
  l.append(list(map(int,input().split())))

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

for j in range(w+1):
  dp[0][j] = 0


def dphoi(i,j):
  #print(i,j)
  if dp[i][j] >= 0: 
    return dp[i][j]
  else:
    
    if j < l[i-1][0]:
      dp[i][j] = dphoi(i-1,j)
      
    else:    
      dp[i][j] = max(dphoi(i-1,j),dphoi(i-1,j-l[i-1][0]) + l[i-1][1])
  
  return dp[i][j]

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

print(dphoi(n,w))

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
numbers=[]
for _ in range(N):
    w,v=input().split()
    numbers.append([int(w),int(v)])
def chmax(a,b):
    if a>=b:
        return a
    else:
        return b
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for a in range(N):
    for sum_w in range(W+1):
        if sum_w-numbers[a][0]>=0:
            dp[a+1][sum_w]=chmax(dp[a+1][sum_w],dp[a][sum_w-numbers[a][0]]+numbers[a][1])
        dp[a+1][sum_w]=chmax(dp[a+1][sum_w],dp[a][sum_w])
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
w_list = []
v_list = []
for i in range(N):
  a,b = map(int,input().split())
  w_list.append(a)
  v_list.append(b)
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

  #DP
for i in range(N):
    for w in range(W+1):
      if w_list[i] <= w:
        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]
#dp[i][w]はi-1番目までのアイテムまで選んだ時のwを超えない最大値
print(dp[N][W])

Submission status: Time Limit Exceeded

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

w, v = list(), list()
w.append(0)
v.append(0)
for i in range(0, n):
    weight, value = map(int, input().split())
    w.append(weight)
    v.append(value)

dp = list()
for i in range(n+1):
    d = [0]*(W+1)
    dp.append(d)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,w = map(int,input().split())
w_i = [0]
v_i = [0]
for i in range(n):
  temp = list(map(int,input().split()))
  w_i.append(temp[0])
  v_i.append(temp[1])

dp = np.zeros(((n+1),(w+1)))

for i in range(1,n+1):
#  print(dp)
  for j in range(w+1):
    temp_1 = -float("inf")
    if j-w_i[i] >= 0:
      temp_1 = dp[i-1][j-w_i[i]] + v_i[i]
    
    temp_2 = dp[i-1][j]
    
    if temp_1 <= temp_2:
      dp[i][j] = temp_2
    elif temp_2 < temp_1:
      dp[i][j] = temp_1
      
print(int(dp[n][w]))

Submission status: Time Limit Exceeded

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

for i in range(n):
  l.append(list(map(int,input().split())))

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

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

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

n,w = MI()
item = []
for i in range(n):
	item.append(LI())

def main():
	dp = [0]*(w+1)
	for i in range(n):
		for j in range(w,item[i][0]-1,-1):
			dp[j] = max(dp[j], dp[j-item[i][0]]+item[i][1])
	print(dp[w])

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

n,w = MI()
item = []
mem = [[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
	item.append(LI())

def rec(i,w):
	if mem[i][w]!=0:
		return mem[i][w]
	if i == n:
		res = 0
	else:
		if w < item[i][0]:
			res = rec(i+1,w)
		else:
			res = max(rec(i+1,w), rec(i+1,w-item[i][0])+item[i][1])
	mem[i][w]=res
	return res


def main():
	print(rec(0,w))

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
#%%
N, W = [int(i) for i in input().split()]
weight, value = [0] * (N + 1), [0] * (N + 1)
for i in range(1, N + 1):
    weight[i], value[i] = [int(i) for i in input().split()]
#%%
import  numpy as np
dp = np.zeros((N + 1, W + 1))

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N, W = [int(x) for x in stdin.readline().rstrip().split()]
dp = [[0]*(W+1) for i in range(N+1)]
cnt = [[0]*(W+1) for i in range(N+1)]
a = []
b = []

for i in range(N):
    A, B = [int(x) for x in stdin.readline().rstrip().split()]
    a.append(A)
    b.append(B)

for n in range(1,N+1):
    for w in range(1,W+1):
        if  w-a[n-1] >= 0:
            
            dp[n][w] = max(dp[n-1][w],dp[n-1][w-a[n-1]]+b[n-1])
            
            if dp[n-1][w] >= dp[n-1][w-a[n-1]]+b[n-1]:
                cnt[n][w] = cnt[n-1][w]
            else:
                cnt[n][w] = cnt[n-1][w-a[n-1]] + 1
                
        dp[n][w] = max(dp[n-1][w],dp[n][w])
        if dp[n][w] == dp[n-1][w]:
            cnt[n][w] = cnt[n-1][w]
        #cnt[n][w] = cnt[n-1][w]

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [[None]*(w+1) for _ in range(n+1)]
    dp[0] = [0]*(w+1)
    for i in range(1, n+1):
        wi, vi = wv[i-1]
        di = dp[i]
        dio = dp[i-1]
        for j in range(wi):
            di[j] = dio[j]
        for j in range(wi, w+1):
            di[j] = max(dio[j], dio[j-wi]+vi)
    print(dp[-1][-1])

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 = [[None]*(w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)
for i in range(1, n+1):
    wi, vi = wv[i-1]
    di = dp[i]
    dio = dp[i-1]
    for j in range(wi):
        di[j] = dio[j]
    for j in range(wi, w+1):
        di[j] = max(dio[j], dio[j-wi]+vi)
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

weight_items = [-1]*n
value_items = [-1]*n

for i in range(n):
    weight_items[i], value_items[i] = map(int,input().split())

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

for num_items in range(n):
    for cap in range(nap_cap+1):
        if(weight_items[num_items] <= cap):
            dp[num_items+1][cap] = max(dp[num_items][cap], dp[num_items][cap - weight_items[num_items]] + value_items[num_items])
        else:
            dp[num_items+1][cap] = dp[num_items][cap]
        #print(dp[num_items+1])

print(dp[n][nap_cap])

Submission status: Time Limit Exceeded

Solution code:
n,wei = [int(x) for x in input().split()]
w = []
v = []
for _ in range(n):
    a,b = [int(x) for x in input().split()]
    w.append(a)
    v.append(b)
dp = [[-1]*(wei+1) for x in range(n+1)]
for i in range(wei+1):
    dp[0][i] = 0

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

print(dp[n][wei])

Submission status: Time Limit Exceeded

Solution code:
N, W, *A = map(int, open(0).read().split())
A = zip(*[iter(A)]*2)

# dp[i][j] iまでの品物からいくつか選んで残り容量がjのときの価値の最大値
dp = [[0]*(W+1) for _ in range(N+1)]

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

print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,w=map(int,raw_input().split())

ans=[]
for i in range(n):
    z=list(map(int,raw_input().split()))
    ans.append(z)
dps=[[0 for i in range(w+1)] for i in range(n+1)]
vi=[[0 for i in range(w+1)] for i in range(n+1)]
#first index denotes row number , second denotes coloumn number
inde=0
def dp(w,inde):
    
    if(w<=0):
        return 0;
    if(inde>=n):
        return 0;
    
    if(vi[inde][w]):
        return dps[inde][w];
    vi[inde][w]=1
    
    if(w-ans[inde][0]==0 or dp(w-ans[inde][0],inde+1)!=0):
        dps[inde][w]=max(dp(w,inde+1),(dp(w-ans[inde][0],inde+1)+ans[inde][1]))
    else:
        dps[inde][w]=dp(w,inde+1)
        
    return dps[inde][w];

maxa=0
#driver code for finding out maximum of array
for i in range(n+1):
    for j in range(w+1):
        dps[i][j]=dp(j,i)
        maxa=max(maxa,dps[i][j])

print(maxa)

Submission status: Time Limit Exceeded

Solution code:

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

ans=[]
for i in range(n):
    z=list(map(int,raw_input().split()))
    ans.append(z)
dps=[[0 for i in range(w+1)] for i in range(n+1)]
vi=[[0 for i in range(w+1)] for i in range(n+1)]
#first index denotes row number , second denotes coloumn number
inde=0
def dp(w,inde):
    
    if(w<=0):
        return 0;
    if(inde>=n):
        return 0;
    
    if(vi[inde][w]):
        return dps[inde][w];
    vi[inde][w]=1
    
    if(w-ans[inde][0]==0 or dp(w-ans[inde][0],inde+1)!=0):
        dps[inde][w]=max(dp(w,inde+1),(dp(w-ans[inde][0],inde+1)+ans[inde][1]))
    else:
        dps[inde][w]=dp(w,inde+1)
        
    return dps[inde][w];

maxa=0
#driver code for finding out maximum of array
for i in range(n+1):
    for j in range(w+1):
        dps[i][j]=dp(j,i)
        maxa=max(maxa,dps[i][j])

print(maxa)

Submission status: Time Limit Exceeded

Solution code:
import sys
x=100000000
sys.setrecursionlimit(x)
input=sys.stdin.readline
n,w=map(int,input().split())
ans=[]
for i in range(n):
    z=list(map(int,input().split()))
    ans.append(z)
dps=[[0 for i in range(w+1)] for i in range(n+1)]
vi=[[0 for i in range(w+1)] for i in range(n+1)]
#first index denotes row number , second denotes coloumn number
inde=0
def dp(w,inde):
    
    if(w<=0):
        return 0;
    if(inde>=n):
        return 0;
    
    if(vi[inde][w]):
        return dps[inde][w];
    vi[inde][w]=1
    
    if(w-ans[inde][0]==0 or dp(w-ans[inde][0],inde+1)!=0):
        dps[inde][w]=max(dp(w,inde+1),(dp(w-ans[inde][0],inde+1)+ans[inde][1]))
    else:
        dps[inde][w]=dp(w,inde+1)
        
    return dps[inde][w];
 
maxa=0
#driver code for finding out maximum of array
for i in range(w+1):
    dps[0][i]=dp(i,0)
    maxa=max(dps[0][i],maxa)
 
print(maxa)

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
ans=[]
for i in range(n):
    z=list(map(int,input().split()))
    ans.append(z)
dps=[[0 for i in range(w+1)] for i in range(n+1)]
vi=[[0 for i in range(w+1)] for i in range(n+1)]
#first index denotes row number , second denotes coloumn number
inde=0
def dp(w,inde):
    
    if(w<=0):
        return 0;
    if(inde>=n):
        return 0;
    
    if(vi[inde][w]):
        return dps[inde][w];
    vi[inde][w]=1
    
    if(w-ans[inde][0]==0 or dp(w-ans[inde][0],inde+1)!=0):
        dps[inde][w]=max(dp(w,inde+1),(dp(w-ans[inde][0],inde+1)+ans[inde][1]))
    else:
        dps[inde][w]=dp(w,inde+1)
        
    return dps[inde][w];

maxa=0
#driver code for finding out maximum of array
for i in range(w+1):
    dps[0][i]=dp(i,0)
    maxa=max(dps[0][i],maxa)

print(maxa)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,w=map(int,input().split())
ans=[]
for i in range(n):
    z=list(map(int,input().split()))
    ans.append(z)
dps=[[0 for i in range(w+1)] for i in range(n+1)]
vi=[[0 for i in range(w+1)] for i in range(n+1)]
#first index denotes row number , second denotes coloumn number
inde=0
def dp(w,inde):
    
    if(w<=0):
        return 0;
    if(inde>=n):
        return 0;
    
    if(vi[inde][w]):
        return dps[inde][w];
    vi[inde][w]=1
    
    if(w-ans[inde][0]==0 or dp(w-ans[inde][0],inde+1)!=0):
        dps[inde][w]=max(dp(w,inde+1),(dp(w-ans[inde][0],inde+1)+ans[inde][1]))
    else:
        dps[inde][w]=dp(w,inde+1)
        
    return dps[inde][w];

maxa=0
#driver code for finding out maximum of array
for i in range(w+1):
    dps[0][i]=dp(i,0)
    maxa=max(dps[0][i],maxa)

print(maxa)

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
w=min(w,10**5)
ans=[]
for i in range(n):
    z=list(map(int,input().split()))
    ans.append(z)
dps=[[0 for i in range(w+1)] for i in range(n+1)]
vi=[[0 for i in range(w+1)] for i in range(n+1)]
#first index denotes row number , second denotes coloumn number
inde=0
def dp(w,inde):
    
    if(w<=0):
        return 0;
    if(inde>=n):
        return 0;
    
    if(vi[inde][w]):
        return dps[inde][w];
    vi[inde][w]=1
    
    if(w-ans[inde][0]==0 or dp(w-ans[inde][0],inde+1)!=0):
        dps[inde][w]=max(dp(w,inde+1),(dp(w-ans[inde][0],inde+1)+ans[inde][1]))
    else:
        dps[inde][w]=dp(w,inde+1)
        
    return dps[inde][w];

maxa=0
#driver code for finding out maximum of array
for i in range(n+1):
    for j in range(w+1):
        dps[i][j]=dp(j,i)
        maxa=max(maxa,dps[i][j])

print(maxa)

Submission status: Time Limit Exceeded

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

n,w=map(int,input().split())
ans=[]
for i in range(n):
    z=list(map(int,input().split()))
    ans.append(z)
dps=[[0 for i in range(w+1)] for i in range(n+1)]
vi=[[0 for i in range(w+1)] for i in range(n+1)]
#first index denotes row number , second denotes coloumn number
inde=0
def dp(w,inde):
    
    if(w<=0):
        return 0;
    if(inde>=n):
        return 0;
    
    if(vi[inde][w]):
        return dps[inde][w];
    vi[inde][w]=1
    
    if(w-ans[inde][0]==0 or dp(w-ans[inde][0],inde+1)!=0):
        dps[inde][w]=max(dp(w,inde+1),(dp(w-ans[inde][0],inde+1)+ans[inde][1]))
    else:
        dps[inde][w]=dp(w,inde+1)
        
    return dps[inde][w];

maxa=0
for i in range(n+1):
    for j in range(w+1):
        dps[i][j]=dp(j,i)
        maxa=max(maxa,dps[i][j])

print(maxa)

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
ans=[]
for i in range(n):
    z=list(map(int,input().split()))
    ans.append(z)
dps=[[0 for i in range(w+1)] for i in range(n+1)]
vi=[[0 for i in range(w+1)] for i in range(n+1)]
#first index denotes row number , second denotes coloumn number
inde=0
def dp(w,inde):
    
    if(w<=0):
        return 0;
    if(inde>=n):
        return 0;
    
    if(vi[inde][w]):
        return dps[inde][w];
    vi[inde][w]=1
    
    if(w-ans[inde][0]==0 or dp(w-ans[inde][0],inde+1)!=0):
        dps[inde][w]=max(dp(w,inde+1),(dp(w-ans[inde][0],inde+1)+ans[inde][1]))
    else:
        dps[inde][w]=dp(w,inde+1)
        
    return dps[inde][w];

maxa=0
for i in range(n+1):
    for j in range(w+1):
        dps[i][j]=dp(j,i)
        maxa=max(maxa,dps[i][j])

print(maxa)

Submission status: Time Limit Exceeded

Solution code:
class item(object):
    def __init__(self,name,Value,weight):
        self.name=name
        self.value=Value
        self.weight=weight
    def getweight(self):
        return self.weight
    def getname(self):
        return self.name
    def getvalue(self):
        return self.value
    def __str__(self):
        res="<"+str(self.name)+","+str(self.value)+","+str(self.weight)+">"
        return res
def sumV(itemlist):
    result=0
    for i in range(len(itemlist)):
        result+=itemlist[i].getvalue
    return result
def sumW(itemlist):
    result=0
    for i in range(len(itemlist)):
        result+=itemlist[i].getweight
    return result
def maxVal(toConsider,avail,result):
    if toConsider==[] or avail==0:
        result+=0
    elif toConsider[0].getweight()>avail:
        result+=maxVal(toConsider[1:],avail,result)
    else:
        withval=toConsider[0].getvalue()+maxVal(toConsider[1:],avail-toConsider[0].getweight(),result)
        #とるかとらないかを選ぶ
        withoutval=maxVal(toConsider[1:],avail,result)
        if withval>withoutval:
            result+=withval
        else:
            result+=withoutval
    return result
N,W=map(int,input().split())
result=0
items=[]
for i in range(N):
    w,v=map(int,input().split())
    items.append(item(str(i),v,w))
"""for i in range(len(items)):
    print(items[i])"""
print(maxVal(items,W,result))

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main(): #startline-------------------------------------------
    n,W = map(int,input().split())
    wv = [list(map(int,input().split())) for i in range(n)]
    w = [wv[i][0] for i in range(n)]
    v = [wv[i][1] for i in range(n)]
    dp = [[0]*(W+1) for i in range(n+1)]
    for i in range(W):
        dp[n][i] = 0
    for i in range(n-1,-1,-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])
    print(dp[0][W])
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Time Limit Exceeded

Solution code:
def ks(n,w):
    dp=[[0 for i in range(w+1)] for j in range(n+1)]
    for i in range(n+1):
        for j in range(w+1):
            if i==0 or j==0:
                dp[i][j]=0
            elif wt[i-1]>j:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(dp[i-1][j-wt[i-1]]+val[i-1],dp[i-1][j])
    return dp[n][w]

n,w=map(int,input().split())
wt=[]
val=[]
for i in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    val.append(b)
print(ks(n,w))

Submission status: Time Limit Exceeded

Solution code:
def ks(wt,val,w):
    dp=[[0 for i in range(w+1)] for j in range(len(wt)+1)]
    for i in range(len(wt)+1):
        for j in range(w+1):
            if i==0 or j==0:
                dp[i][j]=0
            elif wt[i-1]>j:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(dp[i-1][j-wt[i-1]]+val[i-1],dp[i-1][j])
    return dp[len(wt)][w]

n,w=map(int,input().split())
wt=[]
val=[]
for i in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    val.append(b)
print(ks(wt,val,w))

Submission status: Time Limit Exceeded

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

N,W = 102,10**5+3
# weight,value = [None for _ in range(W)],[None for _ in range(N)]
weight,value = np.empty(W, dtype=int),np.empty(N, dtype=int)
n,w = None,None

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

def solve(n,w):
    global dp, weight

    if w < 0:
        return float('-inf')
    elif n < 0:
        return 0
    elif dp[n][w] != -1:
        return dp[n][w]
    dp[n][w] = max(value[n] + solve(n-1,w-weight[n]),solve(n-1,w))
    return dp[n][w]

def main():
    global n, w, weight, value

    n,w = map(int,input().strip().split())
    weight,value = np.empty(w, dtype=int),np.empty(n, dtype=int)
    for _ in range(n):
        weight[_],value[_] = map(int,input().strip().split())

    print(solve(n-1,w))

main()

Submission status: Time Limit Exceeded

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

N,W = 102,10**5+3
# weight,value = [None for _ in range(W)],[None for _ in range(N)]
weight,value = np.empty(W, dtype=int),np.empty(N, dtype=int)
n,w = None,None

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

def solve(n,w):
    global dp, weight

    if w < 0:
        return float('-inf')
    elif n < 0:
        return 0
    elif dp[n][w] != -1:
        return dp[n][w]
    dp[n][w] = max(value[n] + solve(n-1,w-weight[n]),solve(n-1,w))
    return dp[n][w]

def main():
    global n, w, weight, value

    n,w = map(int,input().strip().split())
    for _ in range(n):
        weight[_],value[_] = map(int,input().strip().split())

    print(solve(n-1,w))

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,W = 102,10**5+3
# weight,value = [None for _ in range(W)],[None for _ in range(N)]
weight,value = np.empty(W, dtype=int),np.empty(N, dtype=int)
n,w = None,None

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

def solve(n,w):
    global dp, weight

    if w < 0:
        return float('-inf')
    elif n < 0:
        return 0
    elif dp[n][w] != -1:
        return dp[n][w]
    dp[n][w] = max(value[n] + solve(n-1,w-weight[n]),solve(n-1,w))
    return dp[n][w]

def main():
    global n, w, weight, value

    n,w = map(int,input().strip().split())
    for _ in range(n):
        weight[_],value[_] = map(int,input().strip().split())

    print(solve(n-1,w))

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,W = 102,10**5+3
weight,value = [None for _ in range(W)],[None for _ in range(N)]
n,w = None,None

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

def solve(n,w):
    global dp, weight

    if w < 0:
        return float('-inf')
    elif n < 0:
        return 0
    elif dp[n][w] != -1:
        return dp[n][w]
    dp[n][w] = max(value[n] + solve(n-1,w-weight[n]),solve(n-1,w))
    return dp[n][w]

def main():
    global n, w, weight, value
    
    n,w = map(int,input().strip().split())
    for _ in range(n):
        weight[_],value[_] = map(int,input().strip().split())
    weight = np.array(weight)
    value = np.array(value)
    print(solve(n-1,w))

main()

Submission status: Time Limit Exceeded

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

w = [0] * (N + 1)
v = [0] * (N + 1)

for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())
    
MAX_W = 1000000
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for weight in range(1, W + 1):
        if weight - w[i] >= 0:#入れられる可能性があるかどうか
            dp[i][weight] = max(dp[i][weight], dp[i - 1][weight-w[i]] + v[i])#ある場合は、直前まででLimitがweight-w[i]の最大値と比較
#dp[i][weight] = i-1番目までの品から重さがweight以下になるように選んだ時の価値の最大値
        dp[i][weight] = max(dp[i-1][weight], dp[i][weight])

print(dp[N][W])

Submission status: Time Limit Exceeded

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

import numpy as np
weight = np.empty((110), int)
value = np.empty((110), int)
dp = np.zeros((110, 100010), int)
#print(weight.shape, value.shape, dp.shape)

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

dp[0, :W+1] = 0

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

ans = dp[N, W]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split(" "))
wt,v=[],[]
for i in range(n):
    x,y=map(int,input().split(" "))
    wt.append(x)
    v.append(y)
dp=[[0]*(w+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(w+1):
    dp[0][i]=0
for i in range(1,n+1):
    for j in range(1,w+1):
        if(wt[i-1]<=j):
            dp[i][j]=max(dp[i-1][j-wt[i-1]]+v[i-1],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
    #     print(dp[i][j],end=" ")
    # print()
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
from itertools import product


def read():
    N, W = list(map(int, input().split()))
    pairs = list()
    for i in range(N):
        w, v = list(map(int, input().split()))
        pairs.append((w, v))
    return N, W, pairs

def solve(N, W, pairs):
    dp = [[0 for j in range(W+1)] for i in range(N+1)]
    for i, j in product(range(N), range(W+1)):
        u = dp[i][j]
        if j - pairs[i][0] >= 0:
            u = max(u, dp[i][j-pairs[i][0]]+pairs[i][1])
        dp[i+1][j] = u
    return max(dp[N])

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

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

weightArr = [0] * n
valueArr = [0] * n

for i in range(n):
    weightArr[i] , valueArr[i] = map(int, input().split())

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

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

Submission status: Time Limit Exceeded

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

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

for i in range(n+1):
    if i == 0:
        continue
    for j in range(weight+1):
        case1 = dp[i-1][j]
        if j - items[i-1][0] < 0:
            dp[i][j] = case1
            continue
        else:
            case2 = dp[i-1][j-items[i-1][0]] + items[i-1][1]
            if case1 >= case2:
                dp[i][j] = case1
            else:
                dp[i][j] = case2

print(dp[n][weight])

Submission status: Time Limit Exceeded

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