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 knap(v,wt,n,w,dp):
    if n<0:
        return 0
    if n in dp:
        if w in dp[n]:
            return dp[n][w]
    if wt[n]>w:
        if n in dp:
            dp[n][w]= knap(v,wt,n-1,w,dp)
        else:
            dp[n]={}
            dp[n][w]=knap(v,wt,n-1,w,dp)
        return dp[n][w]
    else:
        if n in dp:
            dp[n][w]= max(v[n]+knap(v,wt,n-1,w-wt[n],dp),knap(v,wt,n-1,w,dp))
        else:
            dp[n]={}
            dp[n][w]= max(v[n]+knap(v,wt,n-1,w-wt[n],dp),knap(v,wt,n-1,w,dp))
        return dp[n][w]
n,w=map(int,input().split())
v,wt=[],[]
for _ in range(n):
    a,b=map(int,input().split())
    v.append(b)
    wt.append(a)
dp={}
ans=knap(v,wt,n-1,w,dp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def knap(v,wt,n,w):
    if n<0:
        return 0
    if wt[n]>w:
        return knap(v,wt,n-1,w)
    else:
        return max(v[n]+knap(v,wt,n-1,w-wt[n]),knap(v,wt,n-1,w))
n,w=map(int,input().split())
v,wt=[],[]
for _ in range(n):
    a,b=map(int,input().split())
    v.append(b)
    wt.append(a)
ans=knap(v,wt,n-1,w)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def knapsack(n,w,v,we,dp):
    if(dp[n][we]!=-1):
        return dp[n][we]

    if(we==0 or n==0):
        dp[n][we]=0
        return 0
    res=0
    if(we<w[n-1]):
        res=knapsack(n-1,w,v,we,dp)
    else:
        res=max(knapsack(n-1,w,v,we,dp),knapsack(n-1,w,v,we-w[n-1],dp)+v[n-1])
        
    dp[n][we]=res
    return res
    

dp=[]
for i in range(101):
    x=[]
    for j in range(100001):
        x.append(-1)
    dp.append(x)

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

    a,b=list(map(int,input().split()))
    w.append(a)
    v.append(b)
val=0
p=knapsack(n,w,v,we,dp)
print(p)

Submission status: Time Limit Exceeded

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

for i in range(x):
    w, v = map(int, input().split())
    for j in range(y, w-1, -1):
        num = dp[j-w]+v
        if num > dp[j]:
            dp[j] = num
print(dp[-1])

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 wk in range(W, w - 1, -1):
        tv = dp[wk - w] + v
        if tv > dp[wk]:
            dp[wk] = tv



print(max(dp))

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 wi, vi in wv:
    for sum_w in range(w, wi - 1, -1):
        v = dp[sum_w - wi] + vi
        if dp[sum_w] < v:
            dp[sum_w] = v

print(dp[w])

Submission status: Time Limit Exceeded

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

for _ in range(n):
    wi, vi = map(int, input().split())
    for sum_w in range(w, wi - 1, -1):
        nv = dp[sum_w - wi] + vi
        if dp[sum_w] < nv:
            dp[sum_w] = nv
print(dp[w])

Submission status: Time Limit Exceeded

Solution code:
n, w = list(map(int, input().split()))
items = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(n):
    for sum_w in range(w + 1):
        if (sum_w - items[i][0]) >= 0:  # i番目の商品を選択
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - items[i][0]] + items[i][1])

        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


def main():
    N, W = map(int, input().split())

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

    dp = np.zeros((N, W + 1), dtype='int')
    for i in range(N):
        for j in range(W + 1):
            if j - w[i] >= 0:
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
P=[]
for _ in range(n):
  iw,iv=map(int,input().split())
  P.append([iw,iv])
INF=float('inf')
 
dp=[[0 for i in range(w+1)] for j in range(n+1)]
 
for i in range(1,n+1):
  for j in range(1,w+1):
    if j-P[i-1][0]>=0:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-P[i-1][0]]+P[i-1][1])
    else:
      dp[i][j]=dp[i-1][j]
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
N, W = [int(i) for i in input().split()]
wv = []
for i in range(N):
  wv.append([int(i) for i in input().split()])
dp = [[0 for i in range(W+1)] for j in range(N+1)]
#print(wv)

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

Submission status: Time Limit Exceeded

Solution code:
'''
in
-----
6 15
6 5
5 6
6 4
6 6
3 5
7 2
'''
'''
out
-----
17
'''
from collections import defaultdict
dp = defaultdict(lambda:int(0))

N, M = map(int, input().split())
W = [0] * (N +2)
V = [0] * (N +2)
for i in range(0, N):
    W[i],V[i] = map(int, input().split())

for i in range(0, N):
    for j in range(0, W[i]+1):
        dp[(i+1,j)] = max(dp[(i+1,j)], dp[(i,j)])
    for j in range(W[i], M+1):
        dp[(i+1,j)] = max(dp[(i+1,j)], dp[(i,j-W[i])] + V[i])

'''
for i in range(0,N+1):
    for j in range(1, M+1):
        print(dp[(i,j)])
    print('')
'''

print(max(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
'''
in
-----
6 15
6 5
5 6
6 4
6 6
3 5
7 2
'''
'''
out
-----
17
'''
from collections import defaultdict
dp = defaultdict(lambda:int(0))

N, M = map(int, input().split())
W = [0] * (N +2)
V = [0] * (N +2)
for i in range(0, N):
    W[i],V[i] = map(int, input().split())

for i in range(0, N):
    for j in range(1, M+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)])

'''
for i in range(0,N+1):
    for j in range(1, M+1):
        print(dp[(i,j)])
    print('')
'''

print(max(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
n, sum_w = map(lambda x: int(x), input().split())

dp = [0]*(sum_w+1)
for _ in range(n):  
    w, v = map(lambda x: int(x), input().split())
    # weightは大きい方から埋めていく必要がある
    for max_w in range(sum_w, w-1, -1):
        dp[max_w] = max(dp[max_w], v + dp[max_w-w])
#     print(dp)
print(dp[sum_w])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, sum_w = map(lambda x: int(x), input().split())

all_weights = []
all_values = []
for _ in range(n):  
    w, v = map(lambda x: int(x), input().split())
    all_weights.append(w)
    all_values.append(v)

dp = [0]*(sum_w+1)

for w, v in zip(all_weights, all_values):
    for max_w in range(sum_w, w-1, -1):
        dp[max_w] = max(dp[max_w], v + dp[max_w-w])
print(dp[sum_w])

Submission status: Time Limit Exceeded

Solution code:
n, sum_w = map(lambda x: int(x), input().split())

# goods = list[]
all_weights = []
all_values = []
for _ in range(n):  
    w, v = map(lambda x: int(x), input().split())
    all_weights.append(w)
    all_values.append(v)
    
memo = {}
    

def max_value(i_item, remaining_weight):
    if (i_item, remaining_weight) in memo.keys():
        return memo[(i_item, remaining_weight)]
    
    if i_item == n - 1:
        memo[(i_item, remaining_weight)] = all_values[i_item] if (all_weights[i_item] <= remaining_weight) else 0
        return memo[(i_item, remaining_weight)]
    
    if all_weights[i_item] > remaining_weight:
        memo[(i_item, remaining_weight)] = max_value(i_item+1, remaining_weight)
        return memo[(i_item, remaining_weight)]
    
    memo[(i_item, remaining_weight)] = max(all_values[i_item] + max_value(i_item+1, remaining_weight - all_weights[i_item]),
        max_value(i_item+1, remaining_weight))
    return memo[(i_item, remaining_weight)]

print(max_value(0, sum_w))

Submission status: Time Limit Exceeded

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

DP = [[0 for j in range(w + 1)] for i in range(n)]
for j in range(W[0], w + 1):
    DP[0][j] = V[0]

for i in range(1, n):
    for j in range(w + 1):
        if j - W[i] >= 0:
            DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i])
        else:
            DP[i][j] = DP[i - 1][j]

print(DP[n - 1][w])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
W=[]
V=[]
for _ in range(n):
    a,b=map(int,input().split())
    W.append(a)
    V.append(b)
dp=[[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    for j in range(w+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][w])

Submission status: Time Limit Exceeded

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

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

for i in range(n):
    w = li[i][0]
    v = li[i][1]
    for k in range(W+1):
        if  w>k:
            dp[i+1][k] = dp[i][k]
            continue
        dp[i+1][k] = max(dp[i][k-w]+v,dp[i][k])
print(dp[n][W])

Submission status: Time Limit Exceeded

Solution code:
def solve(items, W):
    dp = [[0]*(W+1) for _ in range(len(items)+1)]

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

    return dp[len(items)][W]


if __name__ == "__main__":
    N, W = map(int, input().split())
    items = [list(map(int, input().split())) for _ in range(N)]
    print(solve(items, W))

Submission status: Time Limit Exceeded

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

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

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

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def main():
    n, w = map(int, input().split())
    weight_list = []
    value_list = []
    wv_list = []
    for i in range(n):
        weight, value = map(int, input().split())
        weight_list.append(weight)
        value_list.append(value)
    
    dp = [[0] * (w+1) for i in range(n)]
    for i in range(w+1):
        if weight_list[0] <= i:
            dp[0][i] = value_list[0]
    for i in range(1, n):
        for j in range(0, w+1):
            if weight_list[i] <= j:
                # print(dp[i-1][j-weight_list[i]]+value_list[i])
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight_list[i]] + value_list[i])
            else:
                dp[i][j] = dp[i - 1][j]
    print(dp[-1][-1])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, sum_w = map(lambda x: int(x), input().split())

# goods = list[]
all_weights = []
all_values = []
for _ in range(n):  
    w, v = map(lambda x: int(x), input().split())
    all_weights.append(w)
    all_values.append(v)
    
def get_max_value(weights, values, max_sum_weight):
    if (len(weights) <= 0) or (max_sum_weight < min(weights)):
        return 0

    max_value = 0
    for i in range(len(weights)):
        if weights[i] <= max_sum_weight:
            remaining_weights = weights[:i] + weights[i+1:]
            remaining_values = values[:i] + values[i+1:]
            max_value = max(max_value, values[i] + get_max_value(remaining_weights, remaining_values, max_sum_weight - weights[i]))
    return max_value

print(get_max_value(all_weights, all_values, sum_w))

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2020/09/15

@author: harurun
'''
import sys
pin=sys.stdin.readline


N,W=map(int,pin().split())
dp=[[0]*(W+1) for _ in [0]*(N+1)]

for i in range(1,N+1):
  w,v=pin().split()
  w=int(w)
  v=int(v)
  for j in range(W+1):
    if j-w>=0:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
    else:
      dp[i][j]=dp[i-1][j]
print(dp[N][W])
#解説AC

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(1, W+1):
        DP[i][j] = max(DP[i][j-1], DP[i-1][j])
        if j - w >= 0:
            DP[i][j] = max(DP[i][j], DP[i-1][j-w] + v)

print(DP[N][W])

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
vw = [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 vw[i][0]>j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-vw[i][0]]+vw[i][1])
            #[print(*dp[l]) for l in range(n+1)]
            #print("---------------")            
print(dp[n][w])

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def getAnswer(items, w, start):
    if w < 0:
        return -float('inf')
    if w == 0 or start >= len(items):
        return 0
    
    min_ans = 0
    for i in range(start, len(items)):
        min_ans = max(getAnswer(items, w-items[i][0], i+1) + items[i][1], min_ans)
     
    return min_ans


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

items = [list(map(int, input().strip().split())) for i in range(n)]

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    import numpy as np

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

    dp = np.zeros((N * 2, (W + 1)), dtype=np.int64)
    for n in range(N):
        for w in range(W + 1):
            can_w, can_v = products[n]
            if w >= can_w:
                dp[n + 1][w] = max(dp[n + 1][w], dp[n][w - can_w] + can_v)
            dp[n + 1][w] = max(dp[n + 1][w], dp[n][w])
    print(np.max(dp))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, W = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
w, v = [list(i) for i in zip(*l)]
dp = [[0] * (W+1) for i in range(n+1)]
for i in range(1, n+1):
    for j in range(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())
wt = [];c = []
for _ in range(n):
  x,y = map(int,input().split())
  wt.append(x)
  c.append(y)
dp = [[0]*(w+1) for _ in range(n+1)]

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout


def knapsack(i,w):
    if dp[i][w]!=-1:
        return dp[i][w]
    else:
        if w-wi[i]>=0:
            dp[i][w] = max(knapsack(i-1,w-wi[i])+v[i],knapsack(i-1,w))
        else:
            dp[i][w] = knapsack(i-1,w)
        return dp[i][w]
n,w= map(int,input().split())
wi=[0]
v=[0]
for i in range(n):
    x,y= map(int,stdin.readline().split())

    wi.append(x)
    v.append(y)
dp = [[-1 for i in range(w+1)] for j in range(n+1)]
for i in range(w+1):
    dp[0][i]=0
for j in range(n+1):
    dp[j][0]=0
stdout.write(str(knapsack(n,w)) + "\n")
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
def knapsack(i,w):
    if dp[i][w]!=-1:
        return dp[i][w]
    else:
        if w-wi[i]>=0:
            dp[i][w] = max(knapsack(i-1,w-wi[i])+v[i],knapsack(i-1,w))
        else:
            dp[i][w] = knapsack(i-1,w)
        return dp[i][w]
n,w= map(int,input().split())
wi=[0]
v=[0]
for i in range(n):
    x,y= map(int,input().split())

    wi.append(x)
    v.append(y)
dp = [[-1 for i in range(w+1)] for j in range(n+1)]
for i in range(w+1):
    dp[0][i]=0
for j in range(n+1):
    dp[j][0]=0
print(knapsack(n,w))
#print(dp)

Submission status: Time Limit Exceeded

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

print(dp[-1][W])

Submission status: Time Limit Exceeded

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

edu_dp_d_knapsack1()

Submission status: Time Limit Exceeded

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

dp = [[0]*(w+10) for i 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+1][j],dp[i][j])

print(max(dp[-1]))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = map(int, input().split())
dp = np.full((N + 1, W + 1), -np.inf, dtype=np.int64)
dp[0][0] = 0
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W + 1):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        if j + w <= W:
            dp[i + 1][j + w] = max(dp[i + 1][j + w], dp[i][j] + v)
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

# i番目に重さがj以下となるように選んだときの価値の総和の最大値
dp = np.zeros((n, w + 1), dtype=np.int64)

for i in range(0, n):
    for j in range(w + 1):
        # i 番目の品物の重さと価値
        wi, vi = data[i]
        if i == 0:
            take = vi if j - wi >= 0 else 0
            miss = 0
            dp[i][j] = max(take, miss)
        else:
            # i番目の品物を入れる場合
            take = dp[i - 1][j - wi] + vi if j - wi >= 0 else 0
            # 入れない場合
            miss = dp[i - 1][j]
            dp[i][j] = max(take, miss)

print(np.max(dp[n - 1]))

Submission status: Time Limit Exceeded

Solution code:
#ナップサック問題

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

from functools import lru_cache
@lru_cache(maxsize=4098)
def dfs(score,weight,num):
    if weight > w:
        return False
    if num ==n:
        return score
    ret0 = dfs(score + w_vs_s[num][1], weight +w_vs_s[num][0], num+1)
    ret1 = dfs(score,weight,num+1)
    return max(ret0,ret1)


    
print(dfs(0,0,0))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, W = map(int, input().split())
wv = [map(int, input().split()) for i in range(N)]
dp = np.zeros((N+1, W+1), np.int64)
for i, (w, v) in enumerate(wv):
    for j in range(W+1):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j-w >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w] + v)
print(dp[N][W])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for _ in range(n):
    wi, vi = list(map(int, input().split()))
    weights.append(wi)
    values.append(vi)

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):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1] if weights[i-1] <= j else 0)

print(dp[n][w])

Submission status: Time Limit Exceeded

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

ans=[[0]*(W+1) for _ in range(n)]

for i in range(0,n):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        p=0
        if j>=w :
            p=ans[i-1][j-w]+v
        ans[i][j]=max(ans[i-1][j],p)

print(ans[-1][W])

Submission status: Time Limit Exceeded

Solution code:
n,W=map(int,input().split())
values=[]
weights=[]

for _ in range(n):

    a,b=map(int,input().split())
    weights.append(a)
    values.append(b)

ans=[[0]*(W+1) for _ in range(n)]

for i in range(0,n):
    for j in range(1,W+1):
        p=0
        if j>=weights[i] :
            p=ans[i-1][j-weights[i]]+values[i]
        ans[i][j]=max(ans[i-1][j],p)

print(ans[-1][W])

Submission status: Time Limit Exceeded

Solution code:
# 問題D
import numpy as np
import warnings
warnings.filterwarnings('ignore')

#N = "6 15"
#h = "6 5 5 6 6 4 6 6 3 5 7 2"
#N,W = list(map(int, N.split()))
#w = np.array(list(map(int, h.split()))).reshape(N,2)[:,0]
#v = np.array(list(map(int, h.split()))).reshape(N,2)[:,1]

N, W = list(map(int, input().split()))
w = np.array([0] * (N+1))
v = np.array([0] * (N+1))
for i in range(N):
    w[i+1], v[i+1] = map(int, input().split())

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

print(dp[N, W])

Submission status: Time Limit Exceeded

Solution code:
x, y = map(int, input().split())
dp = [[0]*(y+1) for _ in range(x+1)]

for i in range(1, x+1):
    w, v = map(int, input().split())
    for j in range(y+1):
        num0 = dp[i-1][j]
        if j-w >= 0:
            num1 = dp[i-1][j-w]+v
            if num1 > num0:
                dp[i][j] = num1
            else:
                dp[i][j] = num0
        else:
            dp[i][j] = num0
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
x, y = map(int, input().split())
dp = [[-1]*(y+1) for _ in range(x+1)]

for i in range(y+1):
    dp[0][i] = 0

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

Submission status: Time Limit Exceeded

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

for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

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

#dp[i][j] = i番目までのお菓子の中から，ナップサックの中のお菓子の重さの総和がjを超えないようにいくつかお菓子を選んで詰めるとき，価値の最大値

for i in range(1, N+1):
    for j in range(1, W+1):
        if j - w[i] >= 0: #ex.ナップサックの耐加重がj=100,で, i番目のお菓子の重さが20である場合，ナップサックに追加することができるのは，i-1番目までのお菓子でまだ80以下の重さしかないとき。
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i])

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

w[0], v[0] = 0, 0

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

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

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

print(ans[n][W])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

dp = [0] * (W + 1)
dp[w[0]] = v[0]

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

Submission status: Time Limit Exceeded

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


dp=[[0]*(W+1) for _ in range(N+1)]
#初期条件
#dp[0]=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]
print(dp[-1][-1])


"""
def solveDP(N, W, value, weight):
    dp = np.zeros((N+1, W+1))
    
    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]
    
    return dp[N , W]




import numpy as np
N,W = map(int,input().split())
 
dp=np.zeros(W-1, dtype=np.int64)
for _ in range(N):
	w, v = map(int, input().split())



for _ in range(N):
    w,v = map(int,input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])
 
answer = dp.max()
print(answer)
"""

Submission status: Time Limit Exceeded

Solution code:
n,cap=map(int,input().split())
w=[]
v=[]
for _ in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
dp=[[0 for _ in range(cap+1)] for _ in range(n+1)]
for i in range(n+1):
    for c in range(cap+1):
        if c==0 or i==0:
            dp[i][c]=0
        elif c-w[i-1]>=0:
            dp[i][c]=max(dp[i-1][c],dp[i-1][c-w[i-1]]+v[i-1])
        else:
            dp[i][c]=dp[i-1][c]

print(dp[n][cap])

Submission status: Time Limit Exceeded

Solution code:
#Input
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 for j in range(W + 1)] for i in range(N + 1)]
# print(DP)
#Initialization
for i in range(W):
    DP[0][i] = 0

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

# print(DP)
print(DP[N][W])