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

Solution code:
import numpy as np
nw = input().split()
N = int(nw[0])
W = int(nw[1])

dp = np.zeros((W+1, N+1), dtype=np.int64)
#dp = [[0]*(W+1) for i in range(N+1)]

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

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

Submission status: Runtime Error

Solution code:
import psyco

psyco.full()

N,W  = raw_input().split(' ')
N = int(N)
W = int(W)

value = []
weight = []

for i in range(0,N):
	a,b = raw_input().split(' ')
	weight.append(int(a))
	value.append(int(b))

dp = []
for i in range(0,N+1):
	temp = [-1]*(W+1)
	dp.append(temp)

for n in range(0,N+1):
	for w in range(0,W+1):
		if(n == 0 or w == 0):
			dp[n][w] = 0
		else:
			if(w < weight[n-1]):
				dp[n][w] = dp[n-1][w]
			else:
				dp[n][w] = max(dp[n-1][w], dp[n-1][w - weight[n-1]] + value[n-1])

print(dp[N][W])

Submission status: Runtime Error

Solution code:
def knapsack():
    n, max_w = map(int, input().split())
    dp = defaultdict(int)
    dp[0] = 0
    for _ in range(n):
        w, v = map(int, input().split())
        for item in list(dp.keys()):
            dp[item+w] = max(dp[item] + v, dp[item+w])
    max_v = 0
    for w, v in dp.items():
        if w <= max_w:
            max_v = max(v, max_v)
    print(max_v)
    

knapsack()

Submission status: Runtime Error

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

main()

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
wv = [list(map(int, input().split())) for i in range(N)]
dp = [[-1]*10**5 for i in range(N)]
import sys
sys.setrecursionlimit(10**20)
def dfs(i,w):
    if i == N:
        return 0
    if dp[i][w] != -1:
        return dp[i][w]
    else:
        if w+wv[i][0] > W:
            dp[i][w] = dfs(i+1,w)
            return dp[i][w]
        else:
            dp[i][w] = max(dfs(i+1,w+wv[i][0])+wv[i][1], dfs(i+1,w))
    return dp[i][w]
print(max(dfs(0,0), dfs(0,wv[0][0])+wv[0][1]))

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
wv = [list(map(int, input().split())) for i in range(N)]
dp = [[-1]*10**5 for i in range(N)]
import sys
def dfs(i,w):
    if i == N:
        return 0
    if dp[i][w] != -1:
        return dp[i][w]
    else:
        if w+wv[i][0] > W:
            dp[i][w] = dfs(i+1,w)
            return dp[i][w]
        else:
            dp[i][w] = max(dfs(i+1,w+wv[i][0])+wv[i][1], dfs(i+1,w))
    return dp[i][w]
print(max(dfs(0,0), dfs(0,wv[0][0])+wv[0][1]))

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
wv = [list(map(int, input().split())) for i in range(N)]
dp = [[-1]*10**5 for i in range(N)]
import sys
sys.setrecursionlimit(10**9)
def dfs(i,w):
    if i == N:
        return 0
    if dp[i][w] != -1:
        return dp[i][w]
    else:
        if w+wv[i][0] > W:
            dp[i][w] = dfs(i+1,w)
            return dp[i][w]
        else:
            dp[i][w] = max(dfs(i+1,w+wv[i][0])+wv[i][1], dfs(i+1,w))
    return dp[i][w]
print(max(dfs(0,0), dfs(0,wv[0][0])+wv[0][1]))

Submission status: Runtime Error

Solution code:
N,Wmax=map(int,input().split(' '))
info=[ list(map(int,input().split(' '))) for i in range(N) ]
W = info[:][0]
V = info[:][1]

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp = []

for i in range(N):
	if i==0:
		#重量制限がW[0]以上なら荷物を積むのが最善
		dp.append([ V[0] if W[0]<=w else 0 for w in range(Wmax+1) ])	
	else:
		#今回の重量制限をwとする
		#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
		#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
		#よってこの2つのうち大きいほうをdp[i][w]に採用する
		for w in range(Wmax+1):
			val1 = dp[i-1][w-w[i]]+v[i] 
			val2 = dp[i][w] = dp[i-1][w]
			dp.append(max(val1,val2))
print(dp[N-1][Wmax])

Submission status: Runtime Error

Solution code:
N,Wmax=map(int,input().split(' '))
info=[ list(map(int,input().split(' '))) for i in range(N) ]
W = info[:][0]
V = info[:][1]

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp = []

for i in range(N):
	if i==0:
		#重量制限がW[0]以上なら荷物を積むのが最善
		dp.append([ V[0] if W[0]<=w else 0 for w in range(Wmax+1) ])	
	else:
		#今回の重量制限をwとする
		#今回は荷物を積む場合: dp[i][w] = dp[i-1][j-w[i]]+v[i] 
		#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
		#よってこの2つのうち大きいほうをdp[i][w]に採用する
		for w in range(Wmax+1):
			val1 = dp[i-1][j-w[i]]+v[i] 
			val2 = dp[i][w] = dp[i-1][w]
			dp.append(max(val1,val2))
print(dp[N-1][Wmax])

Submission status: Runtime Error

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
W, V = read_col(N, 2)

import numpy as np
# 流れ
# dpテーブルのサイズを決める
#     (N,max(V)*N)
# dpテーブルの初期化
# dpテーブルの更新
#     いままでと同じ
#     sum_v以上を達成すhるように選んだときのsum_wの最小値を保持する
# 答えの抽出
# dpでW以下かつ最大価値が最大(sum_v)なものが答え


dp = np.full((N+1, np.max(V) * N+1), float('inf'))
# dp[:, 0] = 0
dp[0][0] = 0

from itertools import product

for i, sum_v in product(range(N), range(np.max(V) * N+1)):
    if sum_v - V[i] < 0:
        dp[i + 1, sum_v] = dp[i, sum_v]
    else:
        # print(i, sum_v)
        dp[i + 1, sum_v] = min(
            dp[i, sum_v],
            dp[i, sum_v-V[i]]+W[i]
        )

# print(dp)
print(np.where((dp <= K).sum(axis=0) != 0)[0].max())
# print(max(np.where((dp < K).sum(axis=0) != 0)))
# print(max(np.where((dp < K).sum(axis=0) != 0)))

Submission status: Runtime Error

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

for i in range(1, num + 1):
    weight, value = map(int, input().split())
    for w in range(capacity,weight - 1,-1):
        if w < weight:
            continue
        else:
            dp[w] = max( dp[w - weight] + value,  dp[w] )
print(dp[num][capacity])

Submission status: Runtime Error

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

for i in range(1, num + 1):
    weight, value = map(int, input().split())
    for w in range(capacity,w-1,-1):
        if w < weight:
            continue
        else:
            dp[w] = max( dp[w - weight] + value,  dp[w] )
print(dp[num][capacity])

Submission status: Runtime Error

Solution code:
num, capacity = list(map(int, input().split()))
dp = [[0 for i in range(capacity + 1)] for j in range(num + 1)]

for i in range(1, num + 1):
    weight, value = list(map(int, input().split())
    for w in range(capacity + 1):
        if w - weight >= 0:
            dp[i][w] = max( dp[i-1][w - weight] + value,  dp[i-1][w] )
        else:
            dp[i][w] = dp[i-1][w]
print(max( dp[num] ))

Submission status: Runtime Error

Solution code:
n,w_max=map(int,input().split())
W,V=[],[]
for i in range(n):
  w,v=map(int,input().split())
  W.append(w)
  V.append(v)
w_tot=sum(W)
DP=[[0 for i in range(w_tot+1)] for j in range(n)]
for i in range(w_max+1):
  if i>=W[0]:
    DP[0][i]=V[0]
for i in range(1,n):
  for j in range(w_tot+1):
    if j>W[i]:
      DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i]]+V[i])
    elif j==W[i]:
      DP[i][j]=max(DP[i-1][j],V[i])
    else:
      DP[i][j]=DP[i-1][j]
print(DP[n-1][w_max])

Submission status: Runtime Error

Solution code:
n,w_max=map(int,input().split())
W,V=[],[]
for i in range(n):
  w,v=map(int,input().split())
  W.append(w)
  V.append(v)
w_tot=sum(W)
DP=[[0 for i in range(w_tot+1)] for j in range(n)]
DP[0][W[0]]=V[0]
for i in range(1,n):
  for j in range(w_tot+1):
    if j>W[i]:
      DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i]]+V[i])
    elif j==W[i]:
      DP[i][j]=max(DP[i-1][j],V[i])
    else:
      DP[i][j]=DP[i-1][j]
print(DP[n-1][w_max+1])

Submission status: Runtime Error

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

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

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)

l = wvlist[0][0]
for wv in wvlist():
	l = lcm(wv[0],l)
  
dp = np.zeros((N,W+1))
for i, wv in enumerate(wvList):
    for j in range(1, W + 1,l):
        if j - wv[0] >= 0:
            dp[i][j] = np.max(dp[i-1][j-wv[0]] + wv[1], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

print(np.max(dp))

Submission status: Runtime Error

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

weight = []
value = []

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

dp = [0] * (W+1)

for i in range(N+1):
    dp.append([])
    for j in range(W+1):
        dp[i].append(0)


# max value = dp[何個まで見たか][現在の重さ]
for i in range(N):
    for j in range(W+1):
        if (j+weight[i]) <= W:
            dp[i+1][j+weight[i]] = max(dp[i][j+weight[i]], dp[i][j] + value[i])

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

print(dp[N][W])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import Counter
from functools import reduce
import fractions
import pprint
import math
import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]  # LIST INT
def LF(): return [float(x) for x in sys.stdin.readline().split()]  # LIST FLOAT
def LS(): return sys.stdin.readline().split()  # LIST STRING
def MI(): return map(int, sys.stdin.readline().split())  # MAP INT
def II(): return int(sys.stdin.readline())  # INPUT INT
def IS(): return input()  # INPUT STRING
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):  # greatest common divisor
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):  # least common multiple
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


N, W = MI()
dp = [[0 for i in range(20)] for i in range(N+1)]

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

P(max(dp[-1]))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8


def main():
    #raw = ["3 8",
    #       "3 30",
    #       "4 50",
    #       "5 60"]
    #raw = ["5 5",
    #       "1 1000000000",
    #       "1 1000000000",
    #       "1 1000000000",
    #       "1 1000000000",
    #       "1 1000000000"]
    #raw = ["6 15",
    #       "6 5",
    #       "5 6",
    #       "6 4",
    #       "6 6",
    #       "3 5",
    #       "7 2"]
    #N, W = map(int, raw[0].split())
    #data = [list(map(int, x.split())) for x in raw[1:]]
    import sys
    N, W = map(int, sys.stdin.readline().split())
    data = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    #dp = [[0] * (W + 1) for _ in range(N+1)]
    #for i in range(N-1, -1, -1):
    #    for j in range(W+1):
    #        weight, value = data[i]
    #        if j < weight:
    #            dp[i][j] = dp[i+1][j]
    #        else:
    #            dp[i][j] = max(dp[i+1][j], dp[i+1][j - weight] + value)
    #print(dp[0][W])
    dp = [0] * (W + 1)
    mymax = max
    for i in range(N):
        weight, value = data[i]
        for j in range(W, weight-1, -1):
            dp[j] = mymax(dp[j], dp[j - weight] + value)
    print(dp[W])
    pass

from functools import cmp_to_key, lru_cache
def cmp(x, y):
    return -1 if (x[1]+0.0)/x[0] > (y[1]+0.0)/y[0] else 1

@lru_cache(maxsize=None)
def bt(i, c, aux, res):
    if i == N:
        return res
    aux2 = 0
    weight, value = data[i]
    if c != 0:
        c2 = c
        for j in range(i, N):
            if weight <= c2:
                c2 -= weight
                aux2 += value
            else:
                aux2 += (value * c2) / weight
                c2 = 0
    if aux2 + aux <= res:
        return res
    if weight <= c:
        aux3 = aux + value
        if aux3 > res:
            res = aux3
        res = bt(i+1, c - weight, aux3, res)
    return bt(i+1, c, aux, res)

def main2():
    #raw = ["3 8",
    #       "3 30",
    #       "4 50",
    #       "5 60"]
    #raw = ["5 5",
    #       "1 1000000000",
    #       "1 1000000000",
    #       "1 1000000000",
    #       "1 1000000000",
    #       "1 1000000000"]
    #raw = ["6 15",
    #       "6 5",
    #       "5 6",
    #       "6 4",
    #       "6 6",
    #       "3 5",
    #       "7 2"]
    #N, W = map(int, raw[0].split())
    #data = [list(map(int, x.split())) for x in raw[1:]]
    import sys
    N, W = map(int, sys.stdin.readline().split())
    data = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    data.sort(key=cmp_to_key(cmp))
    print(bt(0, W, 0, 0))

main2()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8


def main():
    #raw = ["3 8",
    #       "3 30",
    #       "4 50",
    #       "5 60"]
    #raw = ["5 5",
    #       "1 1000000000",
    #       "1 1000000000",
    #       "1 1000000000",
    #       "1 1000000000",
    #       "1 1000000000"]
    #raw = ["6 15",
    #       "6 5",
    #       "5 6",
    #       "6 4",
    #       "6 6",
    #       "3 5",
    #       "7 2"]
    #N, W = map(int, raw[0].split())
    #data = [list(map(int, x.split())) for x in raw[1:]]
    import sys
    N, W = map(int, sys.stdin.readline().split())
    data = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    #dp = [[0] * (W + 1) for _ in range(N+1)]
    #for i in range(N-1, -1, -1):
    #    for j in range(W+1):
    #        weight, value = data[i]
    #        if j < weight:
    #            dp[i][j] = dp[i+1][j]
    #        else:
    #            dp[i][j] = max(dp[i+1][j], dp[i+1][j - weight] + value)
    #print(dp[0][W])
    dp = [0] * (W + 1)
    mymax = max
    for i in range(N):
        weight, value = data[i]
        for j in range(W, weight-1, -1):
            dp[j] = mymax(dp[j], dp[j - weight] + value)
    print(dp[W])
    pass

from functools import cmp_to_key, lru_cache
def cmp(x, y):
    return -1 if (x[1]+0.0)/x[0] > (y[1]+0.0)/y[0] else 1

@lru_cache(maxsize=None)
def bt(i, c, aux, res):
    if i == N:
        return res
    aux2 = 0
    weight, value = data[i]
    if c != 0:
        c2 = c
        for j in range(i, N):
            if weight <= c2:
                c2 -= weight
                aux2 += value
            else:
                aux2 += (value * c2) / weight
                c2 = 0
    if aux2 + aux <= res:
        return res
    if weight <= c:
        aux3 = aux + value
        if aux3 > res:
            res = aux3
        res = bt(i+1, c - weight, aux3, res)
    return bt(i+1, c, aux, res)

def main2():
    raw = ["3 8",
           "3 30",
           "4 50",
           "5 60"]
    raw = ["5 5",
           "1 1000000000",
           "1 1000000000",
           "1 1000000000",
           "1 1000000000",
           "1 1000000000"]
    raw = ["6 15",
           "6 5",
           "5 6",
           "6 4",
           "6 6",
           "3 5",
           "7 2"]
    N, W = map(int, raw[0].split())
    data = [list(map(int, x.split())) for x in raw[1:]]
    #import sys
    #N, W = map(int, sys.stdin.readline().split())
    #data = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    data.sort(key=cmp_to_key(cmp))
    print(bt(0, W, 0, 0))

main2()

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <queue>
using namespace std;

typedef long long ll;
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(i, n) repi(i, 0, n)
#define rerepi(i, a, b) for(int i = int(a)-1; i >= b; --i)
#define rerep(i, n) rerepi(i, n, 0)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL << 60;

ll N, W;
std::vector<ll> objs_w;
std::vector<ll> objs_v;
ll DP[110][100010];

// ここから開始だよ！
int main() {
	// 呪文エリア
	cin.tie(0);
	ios::sync_with_stdio(false);
	// 詠唱完了
  
  cin >> N >> W;
  rep(i, N) {
    ll w, v;
    cin >> w >> v;
    objs_w.push_back(w);
    objs_v.push_back(v);
  }
  
  DP[0][0] = 0;
  
  rep(nn, N+1) {
    rep(ww, W+1) {
      ll w = objs_w[nn];
      ll v = objs_v[nn];
      
      chmax(DP[nn+1][ww], DP[nn][ww]);
      if (ww - w >= 0) {
        chmax(DP[nn+1][ww], DP[nn][ww - w] + v);
      }
    }
  }
	
  cout << DP[N][W] << endl;
  
	return 0;
}

Submission status: Runtime Error

Solution code:
import sys
 
input = sys.stdin.readline
 
def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)
 
 
n, cap = map(int, input().split())
print(nap(n, cap)

Submission status: Runtime Error

Solution code:
def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)
 
 
n, cap = map(int, input().split())
print(nap(n, cap)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8


def main():
    #raw = ["3 8",
    #       "3 30",
    #       "4 50",
    #       "5 60"]
    #N, W = map(int, raw[0].split())
    #data = [list(map(int, x.split())) for x in raw[1:]]
    import sys
    N, W = map(int, sys.stdin.readline().split())
    data = [list(map(int, x.split())) for x in range(N)]
    dp = [[0] * (W + 1) for _ in range(N+1)]
    for i in range(N-1, -1, -1):
        for j in range(W+1):
            if j < data[i][0]:
                dp[i][j] = dp[i+1][j]
            else:
                dp[i][j] = max(dp[i+1][j], dp[i+1][j - data[i][0]] + data[i][1])
    print(dp[0][W])
    pass

main()

Submission status: Runtime Error

Solution code:
N ,W = map(int,input().split())
L = []
for _ in range(N):
    l = list(map(int,input().split()))
    L.append(l)
dp = [[0 for _ in range(N + 10)] for _ in range(W + 10)]
for i in range(N):
    for w in range(W+1):
        if w+L[i][0] <= W:
            dp[i+1][w+L[i][0]] =max(dp[i][w]+L[i][1], dp[i+1][w+L[i][0]])
        dp[i+1][w] = max(dp[i][w], dp[i+1][w])
ans = 0
for w in range(W+1):
    ans = max(ans,dp[N][w])
print(ans)

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
p = []
for it in test[1:]:
    p.append(list(map(int,input().split())))
    
import numpy as np
dp = np.zeros((N+1,W+1), dtype=np.int64)

i = 0
for w, v in p:
    i += 1
    for w_limit in range(1, W+1):
        if w_limit < w:
            dp[i,w_limit]=dp[i-1,w_limit]
            continue
        if (dp[i-1, w_limit-w] + v) > dp[i-1, w_limit]:
            dp[i, w_limit] = dp[i-1, w_limit-w] + v
        else:
            dp[i,w_limit]=dp[i-1,w_limit]
print(dp.max())

Submission status: Runtime Error

Solution code:
n,w = map(int,input().split())
info = [[0,0]]+[list(map(int,input().split())) for i in range(n)]
v = 0
for i in range(n+1):
  v += info[i][1]
n = n+1
## dp[i][j]:i番目までのアイテムを詰めたときに総価値jになるときの最小重さ
dp = [[float("inf")]*(v) for i in range(n)]

for i in range(n):
  dp[i][0] = 0

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

for j in range(v):
  if dp[n-1][j] <= w:
    ans = j
print(ans)

Submission status: Runtime Error

Solution code:
n, w = [int(i) for i in input().split()]
vals = []
wts = []
for i in range(n):
    ww, vv = [int(i) for i in input().split()]
    vals.append(vv)
    wts.append(ww)

dp = [[-1 for i in range(n+5)] for j in range(sum(wts))]
import sys
sys.setrecursionlimit(10000000)
def brute(weightleft, idx):
    if idx >= n:
        return 0
    if dp[weightleft][idx] != -1:
        return dp[weightleft][idx]
    ans = 10**10
    ans = brute(weightleft, idx+1)
    if wts[idx] <= weightleft:
        ans = max(ans, vals[idx] + brute(weightleft - wts[idx], idx+1))
    dp[weightleft][idx] = ans
    return ans

print(brute(w, 0))

Submission status: Runtime Error

Solution code:
import numpy as np
n, wt = map(int, input().split())
 
d = np.full(n*10**7+1,wt+1, 'i8')
d[0] = 0
for _ in range(n):
  w, v = map(int, input().split())
  d[v:] = np.minimum(d[v:], d[:-v]+w)
print(np.max(np.where(d<=wt)))

Submission status: Runtime Error

Solution code:
import numpy as np
n, wt = map(int, input().split())

d = np.fill(n*10**7+1,wt+1, 'i8')
d[0] = 0
for _ in range(n):
  w, v = map(int, input().split())
  d[v:] = np.minimum(d[v:], d[:-v]+w)
print(np.max(np.where(d<=wt)))

Submission status: Runtime Error

Solution code:
import numpy as np

n,l=map(int,inut().split())
w_all=np.zeros(l+1,dtype=int)

for _ in range(n):
  w,v=map(int,input().split())
  w_all=np.maximum(w_all[w:],w_all[:-w]+v)
  
print(w_all[w])

Submission status: Runtime Error

Solution code:
import numpy as np

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

W = [0] * N
V = [] * N

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

dp = np.zeros((N+1, MAX_W+1), dtype=np.int64)

for i in range(N):
    for j in range(MAX_W+1):
        if j - W[i] >= 0:
            dp[i][j] = np.maximum(dp[i-1][j], dp[i-1][j-W[i]]+V[i])
        else:
            dp[i][j] = dp[i-1][j]

print(dp.max())

Submission status: Runtime Error

Solution code:
import itertools as itr
n, w = list(map(int, input().split()))
warr = [0]*(n+1)
varr = [0]*(n+1)
for i in range(n):
    wi, vi = list(map(int, input().split()))
    warr[i+1] = wi
    varr[i+1] = vi
    
dp = [[0]*(w+1) for _ in range(n+1)]

for i, j in itr.products(range(1,n+1), range(1,w+1)):
        jw = j-warr[i]
        if jw <0:
            dp[i][j] = dp[i-1][j]
            continue
        dp[i][j] = max(dp[i-1][jw] + varr[i], dp[i-1][j])
        
print(dp[n][w])

Submission status: Runtime Error

Solution code:
#include<stdio.h>
int max(int a,int b){
    int h=a;
    if(b>a)h=b;
    return h;
}
int set(int n,int w[],int v[],int W){
    if(n==0){
        return 0;
    }else if(w[n-1]>W){
        return set(n-1,w,v,W);
    }else{
        return max(set(n-1,w,v,W),set(n-1,w,v,W-w[n-1])+v[n-1]);
    }
}
int main(void){
    int N,W;
    scanf("%d%d",&N,&W);
    int v[N],w[N];
    for(int i=0;i<N;i++){
        scanf("%d%d",&v[i],&w[i]);
    }
    printf("%d\n",set(N,w,v,W));
    return 0;
}

Submission status: Runtime Error

Solution code:
from sys import stdin
n, w =  [int(x) for x in stdin.readline().rstrip().split()]
item = []
for i in range(n):
    item.append([int(x) for x in stdin.readline().rstrip().split()])
dp = [[0] * (w + 1) for i in range(n + 1)]
lw = 0
for i in range(1, n + 1):
    for maxw in range(w + 1):
        inw = maxw - item[i - 1][0]
        if dp[i][maxw] < dp[i-1][maxw]
            dp[i][maxw] = dp[i-1][maxw]
        if inw >= 0:
            ndp = dp[i - 1][inw] + item[i - 1][1]
            if dp[i][maxw] < ndp:
                dp[i][maxw] = ndp
print(dp[n][w])

Submission status: Runtime Error

Solution code:
from sys import stdin
n, w =  [int(x) for x in stdin.readline().rstrip().split()]
item = []
for i in range(n):
    item.append([int(x) for x in stdin.readline().rstrip().split()])
dp = [[0] * (w + 1) for i in range(n + 1)]
lw = 0
for i in range(n + 1):
    for maxw in range(w + 1):
        inw = maxw + item[i + 1][0]
        if inw <= w:
            dp[i][inw] = max(dp[i][inw], dp[i][maxw] + item[i + 1][1]
print(dp[n][w])

Submission status: Runtime Error

Solution code:
# using dp with memoization, TLE
from sys import stdin
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)

for n in range(1, N + 1):
    for w in range(W, w - 1, -1):

        dp[w] = max(dp[w], dp[w - s[n - 1][0]] + s[n - 1][1])

print(dp[W])

Submission status: Runtime Error

Solution code:
# using dp with memoization, TLE
from sys import stdin
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)
next_dp = [0] * (W + 1)
for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w >= s[n - 1][0]:
            next_dp[w] = max(next_dp[w], dp[w - s[n - 1][0]] + s[n - 1][1])
    dp = next_dp.copy()
print(dp[W])

Submission status: Runtime Error

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

#weight DP
wdp = [0 for i in range(W)]

for i in range(N):
    update = [i for i in range(W) if wdp[i]>0]
    weight = wv[i][0]
    value = wv[i][1]
    
    # 0 
    if weight <= W:
        wdp[weight] = max(wdp[weight],value)
    
    #update
    for j in update:
        if weight + j <= W:
            wdp[weight+j] = max(wdp[weight+j],wdp[j]+value)

print(max(wdp))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys

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

cf=[(0, 0)]*n

cf = sorted( [[int(x) for x in sys.stdin.readline().split())] for _ in range(n)] )

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we-w)
    for j in range(lim, -1, -1):
        if dp[j+w]<(dp[j] + c) : dp[j+w]=dp[j] + c

print(max(dp))

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
import pandas as pd
import itertools
n,w = map(int,input().split())
df = pd.DataFrame()
for i in range(n):
    tmp = pd.Series(list(map(int,input().split())))
    df = df.append(tmp,ignore_index=True)
cob = []
for i in range(n):
    cob.extend(itertools.combinations(df.index,i+1))
ans = pd.DataFrame()
for i in cob:
    ans = ans.append(df.loc[list(i)].sum(),ignore_index=True)
print(int(max(ans[ans[0]<=w][1])))

Submission status: Runtime Error

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

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

print(max(X))

Submission status: Runtime Error

Solution code:
n,w = (int(i) for i in input().split())
w,v = [],[]
for i in range(n):
    tmp = list(int(i) for i in input().split())
    w.append(tmp[0])
    v.append(tmp[1])

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

tmp = list(range(n))
i_rng = sorted(tmp, reverse=True)
for i in i_rng:
    for j in range(w+1):
        if j<w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]]+v[i])
print(dp[0][w])

Submission status: Runtime Error

Solution code:
import copy

class Item:
	def __init__(self):
		self.weight = 0
		self.value = 0

	def __repr__(self):
		return "(" + str(self.weight) + ", " + str(self.value) + ")"

items: Item = []


def main():
	N, W = [int(x) for x in input().split()]
	global items
	
	for _ in range(0, N):
		x = Item()
		x.weight, x.value = [int(y) for y in input().split()]
		items.append(x)


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

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

	print(dp[N][W])

if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

long long maxValue(vector<vector<long long>> List, int N, int W, int i, int lest, map<vector<int>, long long> memo) {
	if (lest == 0) return 0;
	else if (i == N - 1) {
		if (List[i][0] <= lest) return List[i][1];
		else return 0;
	}
	else {
		vector<int> now = { i, lest };
		auto isthere = memo.find(now);
		if (isthere != memo.end()) return memo[now];
		else {
			long long WithToTake = 0;
			long long WithoutToTake = maxValue(List, N, W, i + 1, lest, memo);
			if (List[i][0] <= lest) {
				WithToTake = List[i][1] + maxValue(List, N, W, i + 1, lest - List[i][0], memo);
			}
			long long ans = max(WithToTake, WithoutToTake);
			memo.insert(make_pair(now, ans));
			return ans;
		}
	}
}

int main() {
	int N, W;
	cin >> N >> W;
	vector<vector<long long>> Items(N, vector<long long>(2));
	for (int i = 0; i < N; i++) {
		cin >> Items[i][0] >> Items[i][1];
	}
	map<vector<int>, long long> memo;
	cout << maxValue(Items, N, W, 0, W, memo) << endl;
}

Submission status: Runtime Error

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

weight = [None] * N
value  = [None] * N

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

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