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^9

1 \leq w_i \leq W

1 \leq v_i \leq 10^3

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

1 1000000000
1000000000 10

Sample Output 2

10

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: Runtime Error

Solution code:
# D
import numpy as np
N,W = map(int, input().split())
# np.maximum https://www.sejuku.net/blog/69175
# 第一引数と第二引数の大小関係を要素ごとに比較して、大きい方を格納した配列を返す
dp = np.zeros(W+1, dtype=np.int64)
# その重さでの最大valueが保存されている
for i in range(N):
    w,v = map(int,input().split())
    # updating dp[w:]
    # total value of dp[k] when i-1 VS total value of dp[k-w]+v when i
    np.maximum(dp[:W-w+1]+v,dp[w:],out=dp[w:])
print(dp[-1])

Submission status: Runtime Error

Solution code:
n,w = map(int, input().split())
a = [[int(x) for x in input().split()] for i in range(n)]
dp = [10**100 for i in range(10**4 + 1)]
dp[0] = 0
for i in range(n):
    for j in range(10**4, -1, -1):
        if dp[j] != 10**100:
            dp[j + a[i][1]] = min(dp[j + a[i][1]], dp[j] + a[i][0])
for i in range(10**4, -1, -1):
    if dp[i] <= w:
        print(i)
        exit(0)

Submission status: Runtime Error

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

def knapsack_base(W, wt, val, n):
    # Base Case 
    if n == 0 or W == 0 : 
        return 0
  
    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if (wt[n-1] > W): 
        return knapsack(W , wt , val , n-1) 
  
    # return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included 
    else: 
        return max(val[n-1] + knapsack(W-wt[n-1] , wt , val , n-1), 
                   knapsack(W , wt , val , n-1))

def knapsack(values,weights,n_items,capacity,return_all=True):
    #check_inputs(values,weights,n_items,capacity)

    table = np.zeros((n_items+1,capacity+1),dtype=np.int)
    keep = np.zeros((n_items+1,capacity+1),dtype=np.int)

    for i in range(1,n_items+1):
        for w in range(0,capacity+1):
            wi = weights[i-1] # weight of current item
            vi = values[i-1] # value of current item
            if (wi <= w) and (vi + table[i-1,w-wi] > table[i-1,w]):
                table[i,w] = vi + table[i-1,w-wi]
                keep[i,w] = 1
            else:
                table[i,w] = table[i-1,w]

    picks = []
    K = capacity

    for i in range(n_items,0,-1):
        if keep[i,K] == 1:
            picks.append(i)
            K -= weights[i-1]

    picks.sort()
    picks = [x-1 for x in picks] # change to 0-index

    if return_all:
        max_val = table[n_items,capacity]
        return picks,max_val
    return picks

def main():
    lines = []
    for line in sys.stdin:
        lines.append([int(i) for i in line.strip().split(' ')])
    n = lines[0][0]
    w = lines[0][1]
    
    wt = np.array(lines[1:])[:,0]
    val = np.array(lines[1:])[:,1]
    #print(knapsack_base(w, wt, val, n))
    print(knapsack(val, wt, n, w)[1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def knapsack_base(W, wt, val, n):
    # Base Case 
    if n == 0 or W == 0 : 
        return 0
  
    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if (wt[n-1] > W): 
        return knapsack(W , wt , val , n-1) 
  
    # return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included 
    else: 
        return max(val[n-1] + knapsack(W-wt[n-1] , wt , val , n-1), 
                   knapsack(W , wt , val , n-1))

def knapsack(values,weights,n_items,capacity,return_all=True):
    #check_inputs(values,weights,n_items,capacity)

    table = np.zeros((n_items+1,capacity+1),dtype=np.int)
    keep = np.zeros((n_items+1,capacity+1),dtype=np.int)

    for i in range(1,n_items+1):
        for w in range(0,capacity+1):
            wi = weights[i-1] # weight of current item
            vi = values[i-1] # value of current item
            if (wi <= w) and (vi + table[i-1,w-wi] > table[i-1,w]):
                table[i,w] = vi + table[i-1,w-wi]
                keep[i,w] = 1
            else:
                table[i,w] = table[i-1,w]

    picks = []
    K = capacity

    for i in range(n_items,0,-1):
        if keep[i,K] == 1:
            picks.append(i)
            K -= weights[i-1]

    picks.sort()
    picks = [x-1 for x in picks] # change to 0-index

    if return_all:
        max_val = table[n_items,capacity]
        return picks,max_val
    return picks

def main():
    lines = []
    for line in sys.stdin:
        lines.append([int(i) for i in line.strip().split(' ')])
    n = lines[0][0]
    w = lines[0][1]
    
    wt = np.array(lines[1:])[:,0]
    val = np.array(lines[1:])[:,1]
    #print(knapsack_base(w, wt, val, n))
    print(knapsack(val, wt, n, w)[1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,w = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(n)]
#dp[i][j]はi番目まででj(j<=w)になるもの
dp = [[0]*(w+1) for i in range(n)]
for k in range(w+1):
  if k >= wv[0][0]:
    dp[0][k] = wv[0][1]
  else:
    continue
for i in range(n-1):
  for j in range(w+1):
    if j >= wv[i+1][0]:
      dp[i+1][j] = max(dp[i][j-wv[i+1][0]]+wv[i+1][1],dp[i][j])
    else:
      dp[i+1][j] = dp[i][j]
print(dp[n-1][w])

Submission status: Runtime Error

Solution code:
import numpy as np
n, w = map(int, input().split())
ndp = np.zeros(w+1)

for i in range(n):
    wi, vi = map(int, input().split())
    np.maximum(ndp[:-wi]+vi, ndp[wi:], out=ndp[wi:])

print(int(ndp[-1]))

Submission status: Runtime Error

Solution code:
# # Educational DP Contest E
# 方針：dp[i][w] := i番目の物の中から，重さwを超えない時の価値の最大値
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
wv.sort()
if N == 1:
    if wv[0][0] <= W:
        print(wv[0][1])
    else:
        print(0)
    exit()

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


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

Submission status: Runtime Error

Solution code:
# # Educational DP Contest E
# 方針：dp[i][w] := i番目の物の中から，重さwを超えない時の価値の最大値
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
wv.sort()
dp = [[0] * (W+1) for _ in range(N+1)]
weight_possible_now = wv[0][0]
if N == 1:
    if wv[0][0] <= W:
        print(wv[0][1])
    else:
        print(0)
    exit()

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import numpy as np
N,W=map(int,input().split())
Weight=[]
Value=[]

for i in range(N):
  w,v = map(int,input().split())
  Weight += [w]
  Value += [v]
DP = np.zeros(W+1, dtype=int)

for i in range(N):
  DP[Weight[i]:]=np.maximum(DP[:-Weight[i]]+Value[i],DP[Weight[i]:])
  #print(DP)
print(DP[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N,W=map(int,input().split())
Weight=[]
Value=[]

for i in range(N):
  w,v = map(int,input().split())
  Weight += [w]
  Value += [v]
  
DP = np.zeros(W+1, dtype=int)

for i in range(N):
  DP[Weight[i]:]=np.maximum(DP[:-Weight[i]]+Value[i],DP[Weight[i]:])
  #print(DP)
print(DP[-1])

Submission status: Runtime Error

Solution code:
# dp[i][j]: i+1個の品物から価値がj以上になるように選んだときの重量の最小値

dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - v[i] >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])
        else:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

# dp[N][j]がW以下であるときのｊの最大値
ans = []
for j in range(V+1):
    if dp[N][j] <= W:
        ans.append(j)
print(max(ans))

Submission status: Runtime Error

Solution code:
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)
V=sum(v)+1
dp=[10**10 for i in range(sum(v)+1)]
dp[0]=0
for i in range(n):
    for j in range(V,-1,-1):
        if dp[j]!=10**10:
            dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i])
for i in range(V,-1,-1):
    if dp[i]<=W:
        print(i)
        exit()

Submission status: Runtime Error

Solution code:
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)
V=sum(v)+1
dp=[10**10 for i in range(sum(v)+1)]
dp[0]=0
for i in range(n):
    for j in range(V,-1,-1):
        if dp[j]!=10**10:
            dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[j])
for i in range(V,-1,-1):
    if dp[i]<=W:
        print(i)
        exit()

Submission status: Runtime Error

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

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

inf = float('inf')
dp = [[inf] * (Vmax+1) for _ in range(N)]
dp[0][0] = 0
dp[0][v[0]] = w[0]

for i in range(1,N):
    for j in range(Vmax):

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

            if dp[i-1][j] + w[i] <= W:
                dp[i][j+v[i]] = min(dp[i][j+v[i]], dp[i-1][j] + w[i])
        
ans = 0
for j in range(Vmax):
    if dp[N-1][j] <= W:
        ans = j

print(ans)

Submission status: Runtime Error

Solution code:
def chmin(a,b):
    if a > b:
        return b
    else:
        return a

N, W = map(int, input().split())
w = []
v = []
Vmax = 100 * N

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

inf = float('inf')
dp = [[inf] * (Vmax+1) for _ in range(N)]
dp[0][0] = 0
dp[0][v[0]] = w[0]

for i in range(1,N):
    for j in range(Vmax):

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

            if dp[i-1][j] + w[i] <= W:
                dp[i][j+v[i]] = chmin(dp[i][j+v[i]], dp[i-1][j] + w[i])
        
for j in range(Vmax):
    if dp[N-1][j] != inf:
        ans = j

print(ans)

Submission status: Runtime Error

Solution code:
x,y=map(int,input().split())
yo=[]
yo0=[]
for __ in range(x):
    a,b=map(int,input().split())
    yo.append(a)
    yo0.append(b)
lol=[0]*(y+1)
lol0=[0]*(y+1)
k=[0]*(y+1)
#print(lol,lol0)
for i in range(1,x+1):
    for j in range(1,y+1):
        if j<yo[i-1]:
            #print(j,lol0[j],lol[j])
            lol0[j]=lol[j]
        else:
            lol0[j]=max(lol[j],yo0[i-1]+lol[j-yo[i-1]])
    lol=lol0[:]
    lol0=k[:]
print(lol[y])

Submission status: Runtime Error

Solution code:
x,y=map(int,input().split())
yo=[]
yo0=[]
for __ in range(x):
    a,b=map(int,input().split())
    yo.append(a)
    yo0.append(b)
lol=[]
for i in range(2):
    lol.append([0]*(y+1))
for i in range(1,x+1):
    for j in range(1,y+1):
        if j<yo[i-1]:
            lol[i%2][j]=lol[(i-1)%2][j]
        else:
            lol[i%2][j]=max(lol[(i-1)%2][j],yo0[i-1]+lol[(i-1)%2][j-yo[i-1]])
print(lol[1][y])

Submission status: Runtime Error

Solution code:
n, w = [int(i) for i in input().split()]
a = [0] * (w + 1)
for _ in range(n):
    b, c = [int(i) for i in input().split()]
    for i in reversed(range(w + 1)):
        if i + b >= w + 1:
            continue
        d = i + b
        a[d] = max(a[d], a[i] + c)
print(a[-1])

Submission status: Runtime Error

Solution code:
N, W = list(map(int, input().split()))
w = []
v = []
for _ in range(N):
    wv = list(map(int, input().split()))
    w.append(wv[0])
    v.append(wv[1])
    
def rec(i, j):
    if dp[i][j]>=0:
        return dp[i][j]
    if i==N:
        res = 0
    elif j<w[i]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-w[i])+v[i])
    dp[i][j] = res
    return res

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

Submission status: Runtime Error

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

dp = [[0]*(W+1) for _ in range(N+1)]
for n in range(1, N+1):
    for w in range(1, W+1):
        if w-WV[n-1][0]>=0:
            dp[n][w] = max(dp[n-1][w], dp[n-1][w-WV[n-1][0]]+WV[n-1][1])
        else:
            dp[n][w] = dp[n-1][w]
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
taple=[]
for i in range(N):
    a,b=map(int,input().split())
    taple.append((a,b))
dp=[[10**22]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    w,v=taple[i-1]
    for j in range(N*(10**3)+1):
        if j>=v[i]:
            dp[i][j]=min(dp[i-1][j-v]+w,dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(N*(10**3),-1,-1):
    if dp[N][i]<=W:
        print(i)
        break

Submission status: Runtime Error

Solution code:
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)
dp=[[10**22]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    for j in range(N*(10**3)+1):
        if j>=v[i]:
            dp[i][j]=min(dp[i-1][j-v[i]]+w[i],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(N*(10**3),-1,-1):
    if dp[N][i]<=W:
        print(i)
        break

Submission status: Runtime Error

Solution code:
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)
dp=[[10**22]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    for j in range(N*(10**3)+1):
        if j>=v[i]:
            dp[i][j]=min(dp[i-1][j-v[i-1]]+w[i-1],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(N*(10**3),-1,-1):
    if dp[N][i]<=W:
        print(i)
        break

Submission status: Runtime Error

Solution code:
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)
dp=[[10**22]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    for j in range(N*(10**3)+1):
        if j>=v[i]:
            dp[i][j]=min(dp[i-1][j-v[i]]+w[i],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(N*(10**3),-1,-1):
    if dp[N][i]<=W:
        print(i)
        break

Submission status: Runtime Error

Solution code:
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)
dp=[[10**22]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    for j in range(N*(10**3)+1):
        if j>=v[i]:
            dp[i][j]=min(dp[i-1][j-v[i]]+w[i],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(N*(10**3),-1,-1):
    if dp[N][i]<=W:
        print(i)
        break

Submission status: Runtime Error

Solution code:
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)
dp=[[10**10]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    for j in range(N*(10**3)+1):
        if j>=v[i]:
            dp[i][j]=min(dp[i-1][j-v[i]]+w[i],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(N*10**3,-1,-1):
    if dp[N][i]<=W:
        print(i)
        break

Submission status: Runtime Error

Solution code:
# coding: utf-8

import numpy as np

"""
20191120
test:
6 8
2 3
1 2
3 6
2 1
1 3
5 85
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())
    V = sum(vs)

    # initialize
    dp = [[None for _ in range(V+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    dp[0][vs[0]] = ws[0]
    existance[0].add(vs[0])

    for n in range(N-1):
        for v in existance[n]:
            # not-use-update
            # if dp[n+1][v] is None:
            #     dp[n+1][v] = dp[n][v]
            # else:
            #     dp[n+1][v] = min(dp[n][v], dp[n+1][v])
            dp[n+1][v] = dp[n][v]

            existance[n+1].add(v)

            # use-update
            if dp[n+1][v+vs[n+1]] is None:
                if dp[n][v] + ws[n+1] <= W:
                    dp[n+1][v+vs[n+1]] = dp[n][v] + ws[n+1]
                    existance[n+1].add(v+vs[n+1])
            else:
                dp[n+1][v+vs[n+1]] = min(dp[n][v] + vs[n+1], dp[n+1][v+vs[n+1]])
                existance[n+1].add(v+vs[n+1])

    ans = 0
    for v in range(V, 0, -1):
        if dp[-1][v] is not None:
            ans = v
            break

    return ans


def miss_main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

    # initialize
    dp = [[None for _ in range(W+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    if W >= ws[0]:
        dp[0][ws[0]] = vs[0]
        existance[0].add(ws[0])

    for n in range(N-1):
        for w in existance[n]:
            # not-use-update
            if dp[n+1][w] is None:
                dp[n+1][w] = dp[n][w]
            else:
                dp[n+1][w] = max(dp[n][w], dp[n+1][w])
            existance[n+1].add(w)

            # use-update
            if w + ws[n+1] <= W:
                if dp[n+1][w+ws[n+1]] is None:
                    dp[n+1][w+ws[n+1]] = dp[n][w] + vs[n+1]
                else:
                    dp[n+1][w+ws[n+1]] = max(dp[n][w] + vs[n+1], dp[n+1][w+ws[n+1]])
                existance[n+1].add(w+ws[n+1])
    # print(np.array(dp))

    ans = 0
    for w in range(1, W+1):
        if dp[-1][w] is not None and dp[-1][w] > ans:
            ans = dp[-1][w]

    return ans


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

Submission status: Runtime Error

Solution code:
# coding: utf-8

import numpy as np

"""
20191120
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

    # initialize
    dp = [[None for _ in range(W+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    if W >= ws[0]:
        dp[0][ws[0]] = vs[0]
        existance[0].add(ws[0])

    for n in range(N-1):
        for w in existance[n]:
            # not-use-update
            if dp[n+1][w] is None:
                dp[n+1][w] = dp[n][w]
            else:
                dp[n+1][w] = max(dp[n][w], dp[n+1][w])
            existance[n+1].add(w)

            # use-update
            if w + ws[n+1] <= W:
                if dp[n+1][w+ws[n+1]] is None:
                    dp[n+1][w+ws[n+1]] = dp[n][w] + vs[n+1]
                else:
                    dp[n+1][w+ws[n+1]] = max(dp[n][w] + vs[n+1], dp[n+1][w+ws[n+1]])
                existance[n+1].add(w+ws[n+1])
    # print(np.array(dp))

    ans = 0
    for w in range(1, W+1):
        if dp[-1][w] is not None and dp[-1][w] > ans:
            ans = dp[-1][w]

    return ans


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

Submission status: Runtime Error

Solution code:
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)
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j>=w[i]:
            dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][w])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[N][W])

Submission status: Runtime Error

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

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

print(dp[n][w])

Submission status: Runtime Error

Solution code:
import sys

import numpy as np

readline = sys.stdin.buffer.readline


def main():
    N, W = map(int, readline().split())
    WV = np.array([[int(x) for x in readline().split()] for _ in range(N)])

    dp = np.zeros([N+1, W+1], np.int64)

    for w, v in WV:
        np.maximum(dp[1:, w:], dp[:-1, :-w] + v, out=dp[1:, w:])

    print(np.max(dp[:, W]))


main()

Submission status: Runtime Error

Solution code:
from sys import stdin
import numpy as np

ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, W = ds_in()

values = np.zeros(W + 1, dtype=int)  # 重さi以下の最大価値
for _ in range(N):
    pre = values.copy()
    w,v = ds_in()  # [weight, value]
    values[w:] = np.maximum(values[:-w] + v, values[w:])
print(values[-1])

Submission status: Runtime Error

Solution code:
def main():

    N, W = map(int, raw_input().split())
    dp = [0]*(W+1)
 
    for i in xrange(N):
        w, v = map(int, raw_input().split())
        for j in xrange(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x
 
    print dp[-1]

main()

Submission status: Runtime Error

Solution code:
from itertools import count

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 w in range(W+1):
        if w - WV[i][0] >= 0:  # 品物を追加できるとき
            dp[i+1][w] = max(dp[i+1][w], dp[i][w-WV[i][0]] + WV[i][1])
        # できないとき
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])
print(dp[N][W])

Submission status: Runtime Error

Solution code:
INF = 2000000000
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())
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]

# ここからメイン
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1 ,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])

# n個まで使って,重さがlimit_wを超えないで価値が最大のものを求める.
for i in range(sum_v, -1, -1):
    if dp[i] <= W:
		print(i)
		break

Submission status: Runtime Error

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, readline().split()))
    wv = [list(map(int, readline().split())) for _ in range(n)]
    dp = [0] * (w + 1)
    for ww, vv in wv:
        for i in range(w-ww+1, -1, -1):
            if i + ww <= w:
                dp[i+ww] = max(dp[i+ww], dp[i] + vv)
    print(dp[-1])


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
INF = 2000000000
n ,limit_w = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])
for i in range(sum_v ,-1,-1):
    if dp[i] <= limit_w:
		print(i)
		break

Submission status: Runtime Error

Solution code:
INF = 2000000000
n ,limit_w = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])
for i in range(sum_v ,-1,-1):
    if dp[i] <= limit_w:
		print(i)

Submission status: Runtime Error

Solution code:
INF = 2000000000
n ,limit_w= map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1 ,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])
for i in range(sum_v, -1, -1):
    if dp[i] <= limit_w:
		print(i)
		break

Submission status: Runtime Error

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):
    j=W
    while j>=w[i]:
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
        j-=1
print(dp[W])

Submission status: Runtime Error

Solution code:
import numpy as np
N, W = map(int, input().split())
l = sorted([tuple(map(int, input().split())) for i in range(N)], key=lambda x: x[0])
dp = np.zeros(W+1, dtype=int)
for i in range(N):
    w = l[i][0]
    dp[w:] = np.maximum(dp[w:], dp[:-w] + l[i][1])
print(dp[-1])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    w[i],v[i]=map(int,input().split())
dpv=[0]*(k+1)
dpw=[0]*(k+1)
for j in range(n):
    for i in range(k,-1,-1):
        if i-w[j]>=0:
            if dpv[i-w[j]]+v[j]>dpv[i]:
                dpw[i]=dpw[i-w[j]]+w[j]
                dpv[i]=dpv[i-w[j]]+v[j]
        else:
            break
print(max(dpv))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def main():
    N, W = map(int, input().split())
    wi, vi = map(int, input().split())
    dp = [0] * wi + [vi] * (W + 1 - wi)
    for _ in range(1, N):
        wi, vi = map(int, input().split())
        for i in range(W, wi - 1, -1):
            t = dp[i - wi] + vi
            if t > dp[i]:
                dp[i] = t
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


def main():
    N, W = map(int, readline().split())
    wv = map(int, read().split())
    dp = np.zeros(W + 1, np.int64)

    for w, v in zip(wv, wv):
        np.maximum(dp[w:], dp[:-w] + v, out=dp[w:])

    print(dp.max())


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF = 2000000000
n = int(input())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
W = int(input())
V = sum(v)
dp = [[INF for i in range(V + 1)] for j in range(n + 1)]

#ここからメイン
dp[0][0] = 0
for i in range(n):
    for j in range(V + 1):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
ans = 0
for i in range(V + 1):
    if dp[n][i] <= W:
        ans = i
print(ans)

Submission status: Runtime Error

Solution code:
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF=2*10**9
n = int(input())
w=[0]*n
v=[0]*n
for i in range(n):
    x,y = map(int, input().split())
    w[i] = x
    v[i] = y
W = int(input())
max_v=max(v)
dp = [[INF for i in range(n*max_v+1)] for j in range(n+1)]

#ここからメイン
dp[0][0]=0
for i in range(n):
    for j in range(n*max_v+1):
        if j<v[i]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
ans=0
for i in range(n*max_v+1):
    if dp[n][i]<=W:
        ans=i
print(ans)

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
b=[]
for _ in range(n):
  u,v=map(int,input().split())
  b.append((u, v))
dp=[[float("inf")]*(10**3*n+1) for _in range(n+1)]
dp[0][0]=0
res=0
for i in range(n):
  for j in range(10**3*n+1):
    if dp[i][j]!=float("inf"):
      dp[i+1][j]=min(dp[i+1][j],dp[i][j])
      dp[i+1][j+b[i][1]]=min(dp[i+1][j+b[i][1]],dp[i][j]+b[i][0])
for i in range(10**3*n+1):
  dp[-1][i]!=float("inf"):
    res=i
print(res)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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())
    
max_v = sum(v)

dp = [[10**10 for i in range(max_v + 1)] for j in range(N+1)]

for i in range(N):
  for k in range(max_v +1):
      dp[i+1][k] = min(dp[i][k-w[i]]+w[i],dp[i][k])


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