Problem:


Score : 100 points

Problem Statement

There are N items, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.

Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.

Sample Input 2

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

5000000000

The answer may not fit into a 32-bit integer type.

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    n, threshold = map(int, input().split())
    wv = np.array([list(map(int, input().split())) for _ in range(n)], dtype='int')
    weight = wv[:, 0]
    values = wv[:, 1]

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

    for i in range(n):
        for j in range(threshold + 1):
            if j - weight[i] >= 0:
                dp[i + 1, j] = dp[i, j - weight[i]] + values[i]

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

import numpy as np


def main():
    n, threshold = map(int, input().split())
    wv = np.array([list(map(int, input().split())) for _ in range(n)])
    weight = wv[:, 0]
    values = wv[:, 1]

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

    for i in range(n):
        for j in range(threshold + 1):
            if j - weight[i] >= 0:
                dp[i + 1, j] = dp[i, j - weight[i]] + values[i]

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def knapsack(n,w):
    global weight,value,bag
    if(n==0 or w==0):
        return 0
    if(bag[n][w]!=-1):
        return bag[n][w]
    if(weight[n-1]<=w):
        bag[n][w]=max(value[n-1] + knapsack(n-1,w-weight[n-1]),knapsack(n-1,w))
        return bag[n][w]
    else:
        bag[n][w]=knapsack(n-1,w)
        return bag[n][w]
n,w=map(int,input().split())
weight=[]
value=[]
bag=[[-1 for j in range(w+1)] for i in range(n+1)]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
temp=knapsack(n,w)
print(temp)

Submission status: Time Limit Exceeded

Solution code:
def knapsack(n,w):
    global weight,value,bag
    if(n==0 or w==0):
        return 0
    temp=str(n)+' '+str(w)
    if(temp in bag):
        return bag[temp]
    if(weight[n-1]<=w):
        bag[temp]=max(value[n-1] + knapsack(n-1,w-weight[n-1]),knapsack(n-1,w))
        return bag[temp]
    else:
        bag[temp]=knapsack(n-1,w)
        return bag[temp]
n,w=map(int,input().split())
weight=[]
value=[]
bag=dict()
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
temp=knapsack(n,w)
print(temp)

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
t=[[0 for i in range(n+1)] for j in range(w+1)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(weight[j-1]<=i):
            t[i][j]=max(value[j-1]+t[i-weight[j-1]][j-1],t[i][j-1])
        else:
            t[i][j]=t[i][j-1]
print(t[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def knapsack(n,w):
    global weight,value,bag
    if(n==0 or w==0):
        return 0
    if(bag[n][w]!=-1):
        return bag[n][w]
    if(weight[n-1]<=w):
        bag[n][w]=max(value[n-1] + knapsack(n-1,w-weight[n-1]),knapsack(n-1,w))
        return bag[n][w]
    else:
        bag[n][w]=knapsack(n-1,w)
        return bag[n][w]
n,w=map(int,input().split())
weight=[]
value=[]
bag=[[-1 for j in range(w+1)] for i in range(n+1)]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
temp=knapsack(n,w)
print(temp)

Submission status: Time Limit Exceeded

Solution code:
def knapsack(n,w):
    global weight,value,bag
    if(n==0 or w==0):
        return 0
    temp=str(n)+' '+str(w)
    if(temp in bag):
        return bag[temp]
    if(weight[n-1]<=w):
        bag[temp]=max(value[n-1] + knapsack(n-1,w-weight[n-1]),knapsack(n-1,w))
        return bag[temp]
    else:
        bag[temp]=knapsack(n-1,w)
        return bag[temp]
n,w=map(int,input().split())
weight=[]
value=[]
bag=dict()
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
temp=knapsack(n,w)
print(temp)

Submission status: Time Limit Exceeded

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

weights = []
values = []
for _ in range(n):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)


def iterative_knapsack(wt, val, W, n):
    # Take the equations in recursive_knapsack. Change the recursive call to the table t. CHange all instances of n to i and W to j.
    # Also the table t was initialized using the base conditions of recursive_knapsack.
    t = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, W+1):
            # if weight of item less than knapsack
            if wt[i-1]<=j:
                include = val[i-1] + t[i-1][j-wt[i-1]]       # val[n-1] + recursive_knapsack(wt, val, W-wt[n-1], n-1)
                exclude = t[i-1][j]                          # recursive_knapsack(wt, val, W, n-1)
                t[i][j] = max(include, exclude)
            else:
                t[i][j] = t[i-1][j]                          # recursive_knapsack(wt, val, W, n-1)

    return t[n][W]


print(iterative_knapsack(weights, values, W, n))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())

def solve(N, W): 
    dp = [0]*(W+1)
    for i in range(0, N):
        wi, vi = map(int, input().split())
        dp_next = [0] * (W+1)
        for w in range(1, W+1):
            if w >= wi:
                dp_next[w] = max(dp[w - wi] + vi, dp[w])
            else:
                dp_next[w] = dp[w]
        dp = dp_next
    return dp[-1]

print(solve(N, W))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
dp = [0]*(W+1)

for i in range(0, N):
    wi, vi = map(int, input().split())
    dp_next = [0] * (W+1)
    for w in range(1, W+1):
        if w >= wi:
            dp_next[w] = max(dp[w - wi] + vi, dp[w])
        else:
            dp_next[w] = dp[w]
    dp = dp_next
print(dp[-1])

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

#  入力
n, w = map(int, input().split())
wvList = []
wv = np.array([list(map(int, input().split())) for i in range(n)])

#  考えるDPテーブルは
#  重さの総和と使う荷物に関するもの
#  行が重さの上限
#  列が使える荷物の数に相当
dp = np.zeros((w + 1, n + 1), dtype=np.int)
for i in range(1, n + 1):
    #  更新の発想(wに意味はない)
    #  使える荷物が増えたが，利用はしない
    #  dp[w, i] = dp[w, i - 1]
    #  荷物を新しく許可された荷物を使う
    #  dp[w, i] = dp[w - wNew, i-1] + newValue
    #  このうちの価値の大きい方を使う
    dp[:, i] = dp[:, i - 1]
    wNew, vNew = wv[i - 1, 0], wv[i - 1, 1]
    dp[wNew:, :] = np.fmax(dp[wNew:, :], vNew + dp[:-wNew, :])

print(dp[w, n])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

#  入力
n, w = map(int, input().split())
wvList = []
wv = np.array([list(map(int, input().split())) for i in range(n)])

#  考えるDPテーブルは
#  重さの総和と使う荷物に関するもの
#  行が重さの上限
#  列が使える荷物の数に相当
dp = np.zeros((w + 1, n + 1), dtype=np.int)
for i in range(1, n + 1):
    #  更新の発想(wに意味はない)
    #  使える荷物が増えたが，利用はしない
    #  dp[w, i] = dp[w, i - 1]
    #  荷物を新しく許可された荷物を使う
    #  dp[w, i] = dp[w - wNew, i-1] + newValue
    #  このうちの価値の大きい方を使う
    dp[:, i] = dp[:, i - 1]
    dp[wv[i - 1, 0]:, :] = np.fmax(
        dp[wv[i - 1, 0]:, :], wv[i - 1, 1] + dp[: -wv[i - 1, 0], :]
    )

print(dp[w, n])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

#  入力
n, w = map(int, input().split())
wvList = []
for i in range(n):
    wvList.append(list(map(int, input().split())))
wv = np.array(wvList)

#  考えるDPテーブルは
#  重さの総和と使う荷物に関するもの
#  行が重さの上限
#  列が使える荷物の数に相当
dp = np.zeros((w + 1, n + 1), dtype=np.int)
for i in range(1, n + 1):
    #  更新の発想(wに意味はない)
    #  使える荷物が増えたが，利用はしない
    #  dp[w, i] = dp[w, i - 1]
    #  荷物を新しく許可された荷物を使う
    #  dp[w, i] = dp[w - wNew, i-1] + newValue
    #  このうちの価値の大きい方を使う
    dp[:, i] = dp[:, i - 1]
    dp[wv[i - 1, 0]:, :] = np.fmax(
        dp[wv[i - 1, 0]:, :], wv[i - 1, 1] + dp[: -wv[i - 1, 0], :]
    )

print(dp[w, n])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,c=map(int,input().split())
    dp=[0]*(c+1)
    final=[]
    for i in range(n):
        x,y=map(int,input().split())
        for j in range(c-x,-1,-1):
           dp[j+x]=max(dp[j+x],dp[j]+y)
    print( max(dp))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#Recursion method
def knapsack(C,n,w,v):
    #if C==0 or n==0:
     #   return 0
    #if w[n-1]>C:
     #   return knapsack(C,n-1,w,v)
    #else:
     #   return max(knapsack(C,n-1,w,v),knapsack(C-w[n-1],n-1,w,v)+v[n-1]) 
     
    dp=[[0 for i in range(C+1)]for _ in range(n+1)]
    for i in range(n+1):
        for j in range(C+1):
            if i==0 or j==0:
                dp[i][j]=0
            elif w[i-1]<=j:
                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]
    return dp[n][C]
def main():
    n,c=map(int,input().split())
    w=[]
    v=[]
    for i in range(n):
        x,y=map(int,input().split())
        w.append(x)
        v.append(y) 
    print(knapsack(c,n,w,v))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#Recursion method
def knapsack(C,n,w,v):
    if C==0 or n==0:
        return 0
    if w[n-1]>C:
        return knapsack(C,n-1,w,v)
    else:
        return max(knapsack(C,n-1,w,v),knapsack(C-w[n-1],n-1,w,v)+v[n-1]) 
        
def main():
    n,c=map(int,input().split())
    w=[]
    v=[]
    for i in range(n):
        x,y=map(int,input().split())
        w.append(x)
        v.append(y) 
    print(knapsack(c,n,w,v))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)

Submission status: Time Limit Exceeded

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

def rec(n, uplimit_w):  
  ans = 0  
  if n == N:  
    return 0  

  # n番目の品物を使えない場合   
  elif wv[n][0] > uplimit_w:  
    return rec(n + 1, uplimit_w)  

  # n番目の品物が使える時  
  # -> n番目の品物は使った方がいいのか、使わない方がいいのか...?  
  else:  
    ans = max(  
      rec(n + 1, uplimit_w),  
      rec(n + 1, uplimit_w - wv[n][0]) + wv[n][1]  
    )  
    return ans  

def solve():  
  print(rec(0, W))  

def main():  
  solve()  

if __name__ == "__main__":  
  main()

Submission status: Time Limit Exceeded

Solution code:
def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


n,W=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,W,w,v))

Submission status: Time Limit Exceeded

Solution code:
n,w = [int(x) for x in input().split(" ")]

dp = [0 for x in range(w+1)]
sf = set([w])
ma = 0
for x in range(n):
    www,vvv = [int(x) for x in input().split(" ")]

    lat = []
    for j in sf:
        if j-www >= 0 and dp[j] + vvv > dp[j-www]:
            dp[j-www] = dp[j] + vvv
            if not (j-www) in sf:
                lat.append(j-www)
            if dp[j] + vvv > ma:
                ma = dp[j] + vvv

    for x in lat:
        sf.add(x)

print(ma)

Submission status: Time Limit Exceeded

Solution code:
n,w = [int(x) for x in input().split(" ")]

dp = [0 for x in range(w+1)]
sf = set([w])
ma = 0
for x in range(n):
    www,vvv = [int(x) for x in input().split(" ")]

    lat = []
    for j in sf:
        if j-www >= 0 and dp[j] + vvv > dp[j-www]:
            dp[j-www] = dp[j] + vvv

            lat.append(j-www)
            if dp[j] + vvv > ma:
                ma = dp[j] + vvv

    for x in lat:
        sf.add(x)

print(ma)

Submission status: Time Limit Exceeded

Solution code:
n,w = [int(x) for x in input().split(" ")]

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

dp = [0 for x in range(w+1)]
sf = [w]
ma = 0
for x in range(n):
    a =len(sf)
    for j in range(a):
        if sf[j]-weights[x] >= 0 and dp[sf[j]] + values[x] > dp[sf[j]-weights[x]]:
            dp[sf[j]-weights[x]] = dp[sf[j]] + values[x]
            sf.append(sf[j]-weights[x])
            if dp[sf[j]] + values[x] > ma:
                ma = dp[sf[j]] + values[x]

print(ma)

Submission status: Time Limit Exceeded

Solution code:
n,w = [int(x) for x in input().split(" ")]

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

dp = [0 for x in range(w+1)]
sf = [w]
for x in range(n):
    a =len(sf)
    for j in range(a):
        if sf[j]-weights[x] >= 0 and dp[sf[j]] + values[x] > dp[sf[j]-weights[x]]:
            dp[sf[j]-weights[x]] = dp[sf[j]] + values[x]
            sf.append(sf[j]-weights[x])
            
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint

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

wv = [list(map(int,input().split())) for _ in range(n)]


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0][0] = 0

for i in range(1,n+1):
    for before_w in range(w):
        #i番目の品物を選ばない場合
        dp_table[i][before_w] = max(dp_table[i][before_w], dp_table[i-1][before_w])
        #i番目の品物を選ぶ場合
        if wv[i-1][0]+before_w <= w and dp_table[i-1][before_w] >= 0:
            dp_table[i][wv[i-1][0]+before_w] = max(dp_table[i][wv[i-1][0]+before_w], dp_table[i-1][before_w] + wv[i-1][1])
        else:
            continue

result = 0

for y in range(w+1):
    tempresult = max(dp_table[n])
    result=max(result,tempresult)

print(result)

#pprint(dp_table)

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

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint

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

wv = [list(map(int,input().split())) for _ in range(n)]


dp_table = [[-float("inf")]*(n+1) for _ in range(w+1)]

dp_table[0][0] = 0

for i in range(1,n+1):
    for before_w in range(w):
        #i番目の品物を選ばない場合
        dp_table[before_w][i] = max(dp_table[before_w][i], dp_table[before_w][i-1])
        #i番目の品物を選ぶ場合
        if wv[i-1][0]+before_w <= w:
            dp_table[wv[i-1][0]+before_w][i] = max(dp_table[wv[i-1][0]+before_w][i], dp_table[before_w][i-1] + wv[i-1][1])
        else:
            continue

result = 0

for y in range(w+1):
    result = max(result,dp_table[y][-1])

print(result)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint

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

wv = [list(map(int,input().split())) for _ in range(n)]


dp_table = [[-float("inf")]*(n+1) for _ in range(w+1)]

dp_table[0][0] = 0

for i in range(1,n+1):
    for before_w in range(w):
        #i番目の品物を選ばない場合
        dp_table[before_w][i] = max(dp_table[before_w][i], dp_table[before_w][i-1])
        #i番目の品物を選ぶ場合
        if wv[i-1][0]+before_w <= w:
            dp_table[wv[i-1][0]+before_w][i] = max(dp_table[wv[i-1][0]+before_w][i], dp_table[before_w][i-1] + wv[i-1][1])
        else:
            continue

result = 0

for y in range(w+1):
    result = max(result,max(dp_table[y]))

print(result)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint

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

wv = [list(map(int,input().split())) for _ in range(n)]


dp_table = [[-float("inf")]*(n+1) for _ in range(w+1)]

dp_table[0][0] = 0

for i in range(1,n+1):
    for before_w in range(w):
        #i番目の品物を選ばない場合
        dp_table[before_w][i] = max(dp_table[before_w][i], dp_table[before_w][i-1])
        #i番目の品物を選ぶ場合
        if wv[i-1][0]+before_w <= w:
            dp_table[wv[i-1][0]+before_w][i] = max(dp_table[wv[i-1][0]+before_w][i], dp_table[before_w][i-1] + wv[i-1][1])
        else:
            continue

result_list=[]

for y in range(w+1):
    result_list.append(max(dp_table[y]))

print(max(result_list))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, W = list(map(int, input().split(' ')))
    items = [list(map(int, input().split(' '))) for _ in range(N)]
    dp = [[0 for _ in range(W + 1)] for _ in range(N)]
    for w in range(items[0][0], W + 1):
        dp[0][w] = items[0][1]
    for n in range(1, N):
        weight, value = items[n]
        for w in range(W + 1):
            if w - weight >= 0:
                dp[n][w] = max([dp[n - 1][w], value + dp[n - 1][w - weight]])
            else:
                dp[n][w] = dp[n - 1][w]
    print(dp[N - 1][W])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

# 入力
N, W = map(int, input().split())
wv = np.array([[int(i) for i in input().split()] for j in range(N)])

# DPテーブル
dp = np.zeros((N+1)*(W+1), dtype=int).reshape((N+1), (W+1))

# DPループ
for i in range(N):    # i番目の荷物について検討する
    for sum_w in range(W+1):    # 遷移の行き先の総重量
        # i番目の荷物を選ぶ場合
        if sum_w - wv[i][0] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-wv[i][0]]+wv[i][1])
        
        # i番目の荷物を選ばない場合
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
        
# 二次元リストの一番右下が最適解
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

# 入力
N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for j in range(N)]

# DPテーブル
dp = np.zeros((N+1)*(W+1), dtype=int).reshape((N+1), (W+1))

# DPループ
for i in range(N):    # i番目の荷物について検討する
    for sum_w in range(W+1):    # 遷移の行き先の総重量
        # i番目の荷物を選ぶ場合
        if sum_w - wv[i][0] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-wv[i][0]]+wv[i][1])
        
        # i番目の荷物を選ばない場合
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
        
# 二次元リストの一番右下が最適解
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n,w = [int(x) for x in input().split(" ")]

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

# maximum sum of values with sumweights < w

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

def d(currentWeight, r):
    if r < 0:
        return 0
    if dp[r][currentWeight] != -1:
        return dp[r][currentWeight]


    c = 0
    if currentWeight + weights[r] <= w:
        c = max(d(currentWeight + weights[r], r - 1) + values[r], d(currentWeight, r - 1))
    else:
        c = d(currentWeight, r - 1)

    dp[r][currentWeight] = c

    return c

print(d(0,n-1))

Submission status: Time Limit Exceeded

Solution code:

def knapSack(W, wt, val, n): 
	K = [[0 for x in range(W+1)] for x in range(n+1)] 

	
	for i in range(n+1): 
		for w in range(W+1): 
			if i==0 or w==0: 
				K[i][w] = 0
			elif wt[i-1] <= w: 
				K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) 
			else: 
				K[i][w] = K[i-1][w] 

	return K[n][W] 




q=list(map(int,input().split()))
n=q[0]
W=q[1]
v=[0]*n
w=[0]*n
for _ in range(n):
  r=list(map(int,input().split()))
  w[_]=r[0]
  v[_]=r[1]
  




print(knapSack(W,w,v,n))

Submission status: Time Limit Exceeded

Solution code:
def knapsack(W,v,w,n,d):
    
    if n<0:
        return 0
    
    if d[W][n]!=-1:
        return d[W][n]
    if w[n]>W:
        d[W][n]=knapsack(W,v,w,n-1,d)
        return d[W][n]
    else:
        d[W][n]=max(v[n]+ knapsack(W-w[n],v,w,n-1,d),knapsack(W,v,w,n-1,d))
        return d[W][n]


q=list(map(int,input().split()))
n=q[0]
W=q[1]
v=[0]*n
w=[0]*n
for _ in range(n):
  r=list(map(int,input().split()))
  w[_]=r[0]
  v[_]=r[1]
  



d=[[-1 for j in range(n+1)] for i in range(W+1)]
print(knapsack(W,v,w,n-1,d))

Submission status: Time Limit Exceeded

Solution code:
# N, W = 3, 8
# ARR = [
#     [3, 30],
#     [4, 50],
#     [5, 60],
# ]
#
# N, W, = 6, 15
# ARR = [
#     [6, 5],
#     [5, 6],
#     [6, 4],
#     [6, 6],
#     [3, 5],
#     [7, 2],
# ]


N,W = map(int,input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int,input().split())))

def calculate(n, w, arr):
    result = [[0] * (w + 1) for i in range(n + 1)]


    for i in range(n):
        width = arr[i][0]
        value = arr[i][1]
        for j in range(w + 1):

            if j >= width:
                result[i + 1][j] = max(result[i][j - width] + value, result[i + 1][j])

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

    # print(result)
    print(result[n][w])


calculate(N, W, ARR)

Submission status: Time Limit Exceeded

Solution code:
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [collections.defaultdict(int) for _ in range(N+1)] #1_indexed
dp[0][0] = 0
for i in range(1,N+1):
    w,v = wv[i-1]
    for dw,dv in dp[i-1].items():
        dp[i][dw] = max(dp[i][dw],dv)
        if w+dw<=W:
            dp[i][w+dw] = max(dp[i][w+dw],v+dv)
print(max(dp[-1].values()))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, W = map(int, input().split())
    item = []
    for _ in range(N):
        w, v = map(int, input().split())
        item.append((w, v))

    dp = [0] * (W + 1)
    for w, v in item:
        for i in range(W + 1)[::-1]:
            if i - w >= 0:
                tmp = dp[i - w] + v
                if tmp > dp[i]:
                    dp[i] = tmp

    print(max(dp))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

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

    print(max(dp[-1]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split() )
w_v = [[0,0]]
for _ in range(n):
	a, b = map(int, input().split() )
	w_v.append([a,b])

dp = [[ 0 for _ in range(n+1)] for i in range(w+1)]
w_v.sort(key=lambda x: x[0])


# if sum(weights) >= w: return sum(v)
for cap in range(w+1):
	for item in range(1,n+1):
		if w_v[item][0] > cap:
			dp[cap][item] = dp[cap][item-1]
		else:
			dp[cap][item] = max(dp[ cap- w_v[item][0] ][item-1] + w_v[item][1], dp[cap][item-1])
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split() )
w_v = [[0,0]]
for _ in range(n):
	a, b = map(int, input().split() )
	w_v.append([a,b])

dp = [[ 0 for _ in range(n+1)] for i in range(w+1)]
w_v.sort(key=lambda x: x[0])


# if sum(weights) >= w: return sum(v)
for cap in range(w+1):
	for item in range(1,n+1):
		if w_v[item][0] > cap:
			break
		before = max([dp[cap-w_v[item][0]][i] for i in range(item)])
		dp[cap][item] = before + w_v[item][1]
print(max(dp[-1]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# 超有名なナップサック問題
N,W_max=map(int,input().split())

W=[]
V=[]
for _ in range(N):
    wi,vi = map(int,input().split())
    W.append(wi)
    V.append(vi)

# dp[i][j] i+1までの荷物を選んだ時の最適な選び方，ただしそのとき（選び終わったあと）の重さはjとする
dp=[[0 for j in range(W_max+1)] for i in range(N)]
dp[0][W[0]] = V[0]

for i in range(N-1):
    for w,d in enumerate(dp[i]):
        if w+W[i+1] > W_max:
            dp[i+1][w] = max(d,dp[i+1][w])
            continue
        dp[i+1][w] = max(d,dp[i+1][w]) # すでに代入されている値と比較する
        dp[i+1][W[i+1]+w] = max(d+V[i+1],dp[i+1][W[i+1]+w])
print(max(dp[N-1]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,W=[int(x) for x in input().rstrip().split()]
l=[]
for i in range(N):
    wv=[int(x) for x in input().rstrip().split()]
    l.append(wv)

dp=[[0 for i in range(W+1)]for j in range(N+1)]#i番目までの品物の中でwを超えない範囲での最高値

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

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
prod = [list(map(int,input().split())) for i in range(n)]

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

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

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