Problem:


Score : 400 points

Problem Statement

You have N items and a bag of strength W.
The i-th item has a weight of w_i and a value of v_i.

You will select some of the items and put them in the bag.
Here, the total weight of the selected items needs to be at most W.

Your objective is to maximize the total value of the selected items.

Constraints

1 ≤ N ≤ 100

1 ≤ W ≤ 10^9

1 ≤ w_i ≤ 10^9

For each i = 2,3,...,N, w_1 ≤ w_i ≤ w_1 + 3.

1 ≤ v_i ≤ 10^7

W, each w_i and v_i are integers.

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 total value of the selected items.

Sample Input 1

4 6
2 1
3 4
4 10
3 4

Sample Output 1

11

The first and third items should be selected.

Sample Input 2

4 6
2 1
3 7
4 10
3 6

Sample Output 2

13

The second and fourth items should be selected.

Sample Input 3

4 10
1 100
1 100
1 100
1 100

Sample Output 3

400

You can take everything.

Sample Input 4

4 1
10 100
10 100
10 100
10 100

Sample Output 4

0

You can take nothing.



Sample input:
4 6
2 1
3 4
4 10
3 4


Sample output:
11

Submission status: Accepted

Solution code:
import numpy as np
N, W0 = map(int, raw_input().split())
items = [map(int, raw_input().split()) for i in range(N)]
w0, _ = items[0]
dp = {}
def dfs(i, W):
    if i < 0:
        return 0
    if (i, W) in dp:
        return dp[i, W]
    w, v = items[i]
    res = dfs(i-1, W)
    if W >= w:
        res = max(res, dfs(i-1, W-w) + v)
    dp[i, W] = res
    return res
print dfs(N-1, W0)

Submission status: Accepted

Solution code:

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

weights = []
values = []
for i in range(N):
    lst = [int(e) for e in input().split()]
    weights.append(lst[0])
    values.append(lst[1])


dp = [{} for j in range(N+1)]

def rec(i, j):
    if j in dp[i]:
        return dp[i][j]

    res = 0
    if i == N:
        res = 0
    elif j < weights[i]:
        res = rec(i+1, j)
    else:
        res = max(
            rec(i+1, j),
            rec(i+1, j-weights[i]) + values[i]
        )

    dp[i][j] = res
    return res


print(rec(0, W))

Submission status: Accepted

Solution code:
# ARC60 D input
nw = list(map(int, input().split()))
N = nw[0]
w_limit = nw[1]

w = []
v = []
for i in range(N):
    wv = list(map(int, input().split()))
    w.append(wv[0])
    v.append(wv[1])

# ARC60 D recursive with memorization
dp = [{} for j in range(N+1)]
def rec_dp(i, j):
    if(j in dp[i]):
        return dp[i][j]
    
    res = 0
    if(i == N):
        res = 0
    elif(j < w[i]):
        res = rec_dp(i+1, j)
    else:
        res = max(rec_dp(i+1, j), rec_dp(i+1, j-w[i]) + v[i])
    
    dp[i][j] = res
    return res

print(rec_dp(0, w_limit))

Submission status: Accepted

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

    w1 = [0, 0]
    w2 = [0, 0]
    w3 = [0, 0]
    w4 = [0, 0]
    v1 = []
    v2 = []
    v3 = []
    v4 = []

    i = 0
    while i < N:
        w, v = map(int, input().split())
        if i == 0 or w == w1[0]:
            w1[0] = w
            w1[1] += 1
            v1.append(v)
        elif w == w1[0] + 1:
            w2[0] = w
            w2[1] += 1
            v2.append(v)
        elif w == w1[0] + 2:
            w3[0] = w
            w3[1] += 1
            v3.append(v)
        elif w == w1[0] + 3:
            w4[0] = w
            w4[1] += 1
            v4.append(v)
        i += 1

    v1.sort(reverse=True)
    v2.sort(reverse=True)
    v3.sort(reverse=True)
    v4.sort(reverse=True)

    ans = []
    for i in range(w1[1] + 1):
        for j in range(w2[1] + 1):
            for k in range(w3[1] + 1):
                for l in range(w4[1] + 1):
                    w = w1[0] * i + w2[0] * j + w3[0] * k + w4[0] * l
                    if w <= W:
                        v = sum(v1[:i] + v2[:j] + v3[:k] + v4[:l])
                        ans.append(v)

    print(max(ans))

main()

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    w1 = [0, 0]
    w2 = [0, 0]
    w3 = [0, 0]
    w4 = [0, 0]
    v1 = []
    v2 = []
    v3 = []
    v4 = []
    i = 0
    while i < N:
        w, v = map(int, input().split())
        if i == 0 or w == w1[0]:
            w1[0] = w
            w1[1] += 1
            v1.append(v)
        elif w == w1[0] + 1:
            w2[0] = w
            w2[1] += 1
            v2.append(v)
        elif w == w1[0] + 2:
            w3[0] = w
            w3[1] += 1
            v3.append(v)
        elif w == w1[0] + 3:
            w4[0] = w
            w4[1] += 1
            v4.append(v)
        i += 1

    v1.sort(reverse=True)
    v2.sort(reverse=True)
    v3.sort(reverse=True)
    v4.sort(reverse=True)

    ans = []
    for i in range(w1[1] + 1):
        for j in range(w2[1] + 1):
            for k in range(w3[1] + 1):
                for l in range(w4[1] + 1):
                    w = w1[0] * i + w2[0] * j + w3[0] * k + w4[0] * l
                    v = sum(v1[:i] + v2[:j] + v3[:k] + v4[:l])
                    if w <= W:
                        ans.append(v)

    print(max(ans))

main()

Submission status: Accepted

Solution code:

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


w=[0 for i in range(N)]
v=[0 for i in range(N)]

Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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


Wmin = min(w)    
w.insert(0,"0")
v.insert(0,"0")
for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]



nap_memo ={}

def nap(i,W2):
    kagi = str(i) + ':' +str(W2)
    if kagi in nap_memo:
        return nap_memo[kagi]
    elif i ==0:
        r=0
    elif W2<Wmin:
        r=0
    elif W2 < w[i]:
        r=nap(i-1,W2)
    elif Wsum[i]<=W2:
        r=Vsum[i]
    else:
        r=max( nap(i-1,W2-w[i])+v[i],nap(i-1,W2))
        
    nap_memo[kagi]=r
    return r

print(nap(N,W))

Submission status: Accepted

Solution code:
N, W = list(map(int, input().split()))
w0, v0 = list(map(int, input().split()))
w_dict = dict()
w_dict[w0] = [v0]
w_dict[w0+1] = list()
w_dict[w0+2] = list()
w_dict[w0+3] = list()

for _ in range(N-1):
    w, v = list(map(int, input().split()))
    w_dict[w].append(v)

w_dict[w0]   = sorted(w_dict[w0],   reverse=True)
w_dict[w0+1] = sorted(w_dict[w0+1], reverse=True)
w_dict[w0+2] = sorted(w_dict[w0+2], reverse=True)
w_dict[w0+3] = sorted(w_dict[w0+3], reverse=True)

max_sum_v = 0
for i_0 in range(len(w_dict[w0])+1):
    for i_1 in range(len(w_dict[w0+1])+1):
        for i_2 in range(len(w_dict[w0+2])+1):
            for i_3 in range(len(w_dict[w0+3])+1):
                sum_w = w0 * i_0 + (w0 + 1) * i_1 + (w0 + 2) * i_2 + (w0 + 3) * i_3
                if sum_w > W:
                    continue
                sum_v = sum(w_dict[w0][:i_0])   + \
                        sum(w_dict[w0+1][:i_1]) + \
                        sum(w_dict[w0+2][:i_2]) + \
                        sum(w_dict[w0+3][:i_3])
                max_sum_v = max(sum_v, max_sum_v)

print(max_sum_v)

Submission status: Accepted

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

wv = [list(map(int, input().split())) for i in range(n)]
cache = [{} for x in range(n)]

def solve(i, w):
    if i >= n:
        return 0

    cache_value = cache[i].get(w)
    if cache_value:
        return cache_value

    if w - wv[i][0] >= 0:
        value = max(solve(i + 1, w), solve(i + 1, w - wv[i][0]) + wv[i][1])
        cache[i][w] = value
        return value
    else:
        value = solve(i + 1, w)
        cache[i][w] = value
        return value

print(solve(0, w))

Submission status: Accepted

Solution code:
N,W=list(map(int,input().split()))
v=[[],[],[],[]]
kosu=[0,0,0,0]
kr=list(map(int,input().split()))
v[0].append(kr[1])
w0=kr[0]
for i in range(1,N):
    kr=list(map(int,input().split()))
    v[kr[0]-w0].append(kr[1])
for i in range(4):
    v[i].sort()
    v[i].reverse()
kos=[len(v[0]),len(v[1]),len(v[2]),len(v[3])]
kk=[-1]*((kos[0]+1)*(kos[1]+1)*(kos[2]+1)*(kos[3]+1))
def toru(a,b,c,d,nw):
    global kk
    if kk[a+(kos[0]+1)*(b+((kos[1]+1)*(c+(kos[2]+1)*d)))]!=-1:
        return kk[a+(kos[0]+1)*(b+((kos[1]+1)*(c+(kos[2]+1)*d)))]
    max=0
    if a<kos[0] and W>=nw+w0 and max<toru(a+1,b,c,d,nw+w0)+v[0][a]:
        max=toru(a+1,b,c,d,nw+w0)+v[0][a]
    if b<kos[1] and W>=nw+w0+1 and max<toru(a,b+1,c,d,nw+w0+1)+v[1][b]:
        max=toru(a,b+1,c,d,nw+w0+1)+v[1][b]
    if c<kos[2] and W>=nw+w0+2 and max<toru(a,b,c+1,d,nw+w0+2)+v[2][c]:
        max=toru(a,b,c+1,d,nw+w0+2)+v[2][c]
    if d<kos[3] and W>=nw+w0+3 and max<toru(a,b,c,d+1,nw+w0+3)+v[3][d]:
        max=toru(a,b,c,d+1,nw+w0+3)+v[3][d]
    kk[a+(kos[0]+1)*(b+((kos[1]+1)*(c+(kos[2]+1)*d)))]=max
    return max
 
 
maxv=toru(0,0,0,0,0)
 
print(maxv)

Submission status: Accepted

Solution code:

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))

Submission status: Accepted

Solution code:
#coding:utf-8

N, W = map(int, raw_input().split(" "))
items = [tuple(map(int, raw_input().split(" "))) for _ in range(N)]
dic = {}

def search(i, j):
    if i == N:
        return 0
    if (i, j) not in dic:
        dic[(i, j)] = search(i + 1, j)
        w, v = items[i]
        if j + w <= W:
            dic[(i, j)] = max(dic[(i, j)] , search(i + 1, j + w) + v)
    return dic[(i, j)]

print search(0, 0)

Submission status: Accepted

Solution code:
# coding: utf-8

if __name__ == "__main__":
	n, w = map(int, input().split())
	vs, ws = [], []

	for i in range(n):
		w_, v_ = map(int, input().split())
		ws.append(w_)
		vs.append(v_)

	nap_memo = {}
	def nap(i, j):
		key = str(i)+':'+str(j)

		if key in nap_memo:
			return nap_memo[key]

		r = 0
		if i == n:
			r = 0
		elif j < ws[i]:
			r = nap(i+1, j)
		else:
			r = max(nap(i+1, j),
					nap(i+1, j-ws[i]) + vs[i])

		nap_memo[key] = r
		return r

	print(nap(0, w))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[tuple(map(int,input().split())) for _ in range(n)]
d = {}
def f(i,j):
    if i==n:
        return 0
    if (i,j) not in d:
        d[i,j]=f(i+1,j)
        w,v=a[i]
        if j+w<=m:
            d[i,j]=max(d[i,j],v+f(i+1,j+w))
    return d[i,j]
print(f(0,0))

Submission status: Accepted

Solution code:
N, W = map(int, raw_input().split())
X = [map(int, raw_input().split()) for _ in range(N)]
 
dp = {}
dp[0] = 0
 
for w, v in X:
    d = dp.copy()
    for k in d:
        if k + w > W:
            continue
        if k + w in dp:
            dp[k + w] = max(dp[k + w], d[k] + v)
        else:
            dp[k + w] = d[k] + v
 
print max(dp.values())

Submission status: Accepted

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]//(x[0] - w1 + 40)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans
	
def f3():
	L.sort(key = (lambda x: - x[1]//x[0]))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans
def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 10000000:
	print(f1())
elif W > 10000000:
	print(f3())
else:
	print(f2())

Submission status: Accepted

Solution code:
#coding=UTF-8

mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
W=int(hyo[1])

weight=[]
values=[]
for idx in range(0,N,1):
    mozir=input()
    hyo=mozir.split(' ')
    weight.append(int(hyo[0]))
    values.append(int(hyo[1]))

minimum_weight=min(weight)
weight_values=list(range(0,4,1))
for idx in range(0,4,1):
    weight_values[idx]=[]

for idx in range(0,N,1):
    weight_values[weight[idx]-minimum_weight].append(values[idx])

for idx in range(0,4,1):
    weight_values[idx].sort(reverse=True)

#print(weight_values)

jogen=min(W//minimum_weight,len(weight_values[0]))

tmpten=[0,0,0]
tmpomo=[0,0,0]
ans=0
for idx in range(0,jogen+1,1):
    tmpten[0]=sum(weight_values[0][0:idx])
    tmpomo[0]=minimum_weight*idx

    jogen=min((W-tmpomo[0])//(minimum_weight+1),len(weight_values[1]))
    for idy in range(0,jogen+1,1):
        tmpten[1]=tmpten[0]+sum(weight_values[1][0:idy])
        tmpomo[1]=tmpomo[0]+(minimum_weight+1)*idy

        jogen=min((W-tmpomo[1])//(minimum_weight+2),len(weight_values[2]))
        for idz in range(0,jogen+1,1):
            tmpten[2]=tmpten[1]+sum(weight_values[2][0:idz])
            tmpomo[2]=tmpomo[1]+(minimum_weight+2)*idz

            kosuu=min((W-tmpomo[2])//(minimum_weight+3),len(weight_values[3]))
            tmpans=tmpten[2]+sum(weight_values[3][0:kosuu])
            #print(tmpans)
            ans=max(ans,tmpans)

print(ans)

Submission status: Accepted

Solution code:
import collections

if __name__ == '__main__':
    N, W = map(int, input().split())

    dp = [collections.defaultdict(int) for _ in range(N + 1)]
    dp[0][0] = 0

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

    ans = max(dp[N].values())
    print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, raw_input().split())
X = [map(int, raw_input().split()) for _ in range(N)]

dp = {}
dp[0] = 0

for w, v in X:
    d = dp.copy()
    for k in d:
        if k + w > W:
            continue
        if k + w in dp:
            dp[k + w] = max(dp[k + w], d[k] + v)
        else:
            dp[k + w] = d[k] + v

print max(dp.values())

Submission status: Accepted

Solution code:
from collections import defaultdict
N, W = map(int, raw_input().split())

w = []
v = []
for i in range(0, N):
    w_i, v_i = map(int, raw_input().split())
    w.append(w_i)
    v.append(v_i)

items = sorted([{'w': w[i], 'v': v[i]} for i in range(0, N)],
               lambda i1, i2: cmp(i2['w'], i1['w']))

def default():
    return defaultdict(lambda:-1)

results = defaultdict(default)

def add(i, w_max):
    if results[i][w_max] != -1:
        return results[i][w_max]

    if i == N:
        return 0;

    if w_max < items[i]['w']:
        res = add(i+1, w_max)
    else:
        res = max(
            add(i+1, w_max),
            add(i+1, w_max - items[i]['w']) + items[i]['v']
        )
    results[i][w_max] = res
    return res

print(add(0, W))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
(N,W) = map(int,input().split(" "))

w = []
v = []

for i in range(N):
    item = list(map(int,input().split(" ")))
    w.append(item[0])
    v.append(item[1])


nap_memo = {}

def nap(i,j):
    key = str(i)+':'+str(j)
    if key in nap_memo:
        return nap_memo[key]
    r = 0
    if i == N:
        r= 0
    elif j < w[i]:
        r= nap(i+1,j)
    else:
        r= max([nap(i+1,j),nap(i+1,j-w[i])+v[i]])

    nap_memo[key] = r
    return r

print(nap(0,W))

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import accumulate
readline = stdin.readline

N, W = map(int, input().split())
vs = [[] for _ in range(4)]
w, v = map(int, input().split())
w1 = w
vs[0].append(v)
for _ in range(N - 1):
    w, v = map(int, input().split())
    vs[w - w1].append(v)

for i in range(4):
    vs[i].sort(reverse=True)
    vs[i] = [0] + list(accumulate(vs[i]))

result = 0
for i in range(len(vs[0]) + 1):
    a = W - w1 * i
    if a < 0:
        break
    for j in range(len(vs[1]) + 1):
        b = a - (w1 + 1) * j
        if b < 0:
            break
        for k in range(len(vs[2]) + 1):
            c = b - (w1 + 2) * k
            if c < 0:
                break
            t = vs[0][i] + vs[1][j] + vs[2][k]
            for l in range(len(vs[3]) + 1):
                d = c - (w1 + 3) * l
                if d < 0:
                    break
                result = max(result, t + vs[3][l])
print(result)

Submission status: Runtime Error

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

n, weight = map(int, input().split())
w, v = [0]*n, [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())

base = w[0]
#q, r = divmod(weight, base)

for i in range(n):
    w[i] -= base

# dp[i][j] = i個選んで重さの余りがjの時の、価値の最大値
dp = [[0] * (3*n) for _ in range(n+1)]

for i in range(n):
    for j in range(i, -1, -1):
        for k in range(3*j+1):
            if dp[j+1][k+w[i]] < dp[j][k] + v[i]:
                dp[j+1][k+w[i]] = dp[j][k] + v[i]

ans = 0
for i in range(n+1):
    for j in range(3*n):
        if base * i + j <= weight and ans < dp[i][j]:
            ans = dp[i][j]

print(ans)

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
w_v = [list(map(int, input().split())) for _ in range(n)]
#dp = [[0]*(W+1) for _ in range(n+1)]
#dp[i][w]はi番目までの品物の中から重さｗ以下なるように選んだときの価値の総和の最大値
dp = [[0]*(W+1) for _ in range(2)]
#dp[0][w]は最新の偶数インデックスの値
#dp[1][w]は最新の奇数インデックスの値
ans = 0
for i in range(n):
    mod = i % 2
    for w in range(W+1):
        dp[mod ^ 1][w] = max(dp[mod ^ 1][w], dp[mod][w])
        if w - w_v[i][0] >= 0:
            dp[mod ^ 1][w] = max(dp[mod ^ 1][w], dp[mod][w - w_v[i][0]] + w_v[i][1])
        ans = max(ans, dp[mod ^ 1][w])
print(ans)

Submission status: Runtime Error

Solution code:
n, W = map(int, input().split())
w_v = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*(W+1) for _ in range(n+1)]
#dp[i][w]はi番目までの品物の中から重さｗ以下なるように選んだときの価値の総和の最大値

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

Submission status: Runtime Error

Solution code:
# 普通のナップサックは O(荷物の数、ナップサックに入る重量の上限)で計算できる。
# 今回はこれだと O(100 * 10**9) なので無理。
# 明らかに条件で重要なのは「すべてのi=2,3,...,Nについて、w_1<=w_i<=w_1+3」

# w_1が1000とする
# W = 4500→4つが必ず入り、5つは必ず入らない。価値の高いものから4つ。
# W = 4005→3つが必ず入る。4つが入るかどうかは場合による。
# max(3つの場合, 4つの場合)。3つは価値の高いものから3つ。4つは?
# 4つ選ぶ、4005以下、価値最大化
# dp[i][k][l]

# w_1〜w_iの中からk個選んで、重量をちょうどlにしたときの、最大価値
# dp[i][k][l] := max(dp[i-1][k][l], dp[i-1][k-1][l - w_i] + v_i)

# w_1〜w_iの中からk個選んで、重量をl以下にしたときの、最大価値
# dp[i][k][l] := max(dp[i-1][k][l], dp[i-1][k-1][l - w_i] + v_i)

# 後者を使うべき。更新式は同じで最後に重量に関してmaxを取る手間が無いので。
# i <= N, k <= N, l <= 3*N

n, w_limit = list(map(int, input().split()))

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

weight_base = baggage[0][0]

# i添字は0〜n-1 問題文から1引いて0-indexにする
# k添字は0〜n 
# l添字は0〜3n

for i in range(n):
    baggage[i][0] -= weight_base

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

for l in range(baggage[0][0], 3*n):
    dp[0][1][l] = baggage[0][1]

for i in range(1, n):
    for k in range(1, n+1):
        for l in range(3*n+1):
            if l - baggage[i][0] >= 0:
                dp[i][k][l] = max(dp[i-1][k][l], dp[i-1][k-1][l - baggage[i][0]] + baggage[i][1])
            else:
                dp[i][k][l] = dp[i-1][k][l]

valid_min_num = w_limit // (weight_base+3)
valid_max_num = w_limit // weight_base

ans = 0
for num in range(valid_min_num, min(valid_max_num, n) + 1):
    weight_rest = w_limit - weight_base * num
    # print(n-1, num, weight_rest)
    ans = max(ans, dp[n-1][num][weight_rest])

print(ans)

Submission status: Runtime Error

Solution code:
def KnapsackDP(N,WMax,WVList):
    DP = [[0]*(WMax+1) for T in range(N+1)]
    
    for I in range(0,N):
        for K in range(0,WMax+1):
            if K<WVList[I][0]:
                DP[I+1][K] = DP[I][K]
            else:
                if DP[I][K]>DP[I][K-WVList[I][0]]+WVList[I][1]:
                    DP[I+1][K] = DP[I][K]
                else:
                    DP[I+1][K] = DP[I][K-WVList[I][0]]+WVList[I][1]
    return DP[N][WMax]
  
N,MaxW = (int(T) for T in input().split())
WVList = [[] for T in range(0,N)]
for T in range(0,N):
    WVList[T] = [int(T) for T in input().split()]
MaxV = KnapsackDP(N,MaxW,WVList)
print(MaxV)

Submission status: Runtime Error

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

dp = [[0]*(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] = 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: Runtime Error

Solution code:
n, w = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(n)]
if w < items[0][0] :
    print(0)
    exit()
w_sum = 0
v_sum = 0
for i in range(n):
    w_sum += items[i][0]
    v_sum += items[i][1]
if w >= w_sum:
    print(v_sum)
    exit()
dp = {}
#for j in range(items[0][0],w+1):
cnt_l = 1
cnt_r = 0
j = items[0][0] * cnt_l + cnt_r
while j < w+1:
    for i in range(1,n+1):
        if j-items[i-1][0] >= 0:
            if str(i-1)+":"+str(j) not in dp:
                dp[str(i - 1) + ":" + str(j)] = 0
            if str(i-1)+":"+str(j-items[i-1][0]) not in dp:
                dp[str(i - 1) + ":" + str(j - items[i - 1][0])] = 0
            dp[str(i)+":"+str(j)] = max(dp[str(i-1)+":"+str(j)],dp[str(i-1)+":"+str(j-items[i-1][0])]+items[i-1][1])
        else:
            if str(i-1)+":"+str(j) not in dp:
                dp[str(i - 1) + ":" + str(j)] = 0
            dp[str(i)+":"+str(j)] = dp[str(i-1)+":"+str(j)]
    cnt_r += 1
    if cnt_r >= 350:
        cnt_l += 1
        cnt_r = 0
    j = items[0][0] * cnt_l + cnt_r
print(dp[str(n)+":"+str(w)])

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(n)]
if w < items[0][0] :
    print(0)
    exit()
w_sum = 0
v_sum = 0
for i in range(n):
    w_sum += items[i][0]
    v_sum += items[i][1]
if w >= w_sum:
    print(v_sum)
    exit()
dp2 = [[0]*(w+1) for _ in range(n+1)]
dp = {}
for j in range(1,w+1):
    for i in range(1,n+1):
        if j-items[i-1][0] >= 0:
            if str(i-1)+":"+str(j) not in dp:
                dp[str(i - 1) + ":" + str(j)] = 0
            if str(i-1)+":"+str(j-items[i-1][0]) not in dp:
                dp[str(i - 1) + ":" + str(j - items[i - 1][0])] = 0
            dp[str(i)+":"+str(j)] = max(dp[str(i-1)+":"+str(j)],dp[str(i-1)+":"+str(j-items[i-1][0])]+items[i-1][1])
        else:
            if str(i-1)+":"+str(j) not in dp:
                dp[str(i - 1) + ":" + str(j)] = 0
            dp[str(i)+":"+str(j)] = dp[str(i-1)+":"+str(j)]
print(dp[str(n)+":"+str(w)])

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def solve1(N, W, weight, value):
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        for w in range(W + 1):
            if w - weight[i] >= 0:
                dp[i + 1][w] = dp[i][w - weight[i]] + value[i]
            if dp[i + 1][w] < dp[i][w]:
                dp[i + 1][w] = dp[i][w]

    return dp[N][W]


def solve2(N, W, weight, value):
    w0 = weight[0]
    M = W // w0
    if M == 0:
        return 0

    weight_adj = [w - w0 for w in weight]
    w_total = sum(weight_adj)

    dp = [[[0] * (w_total + 1) for j in range(N + 1)] for i in range(M + 1)]
    for i in range(M):
        for j in range(N):
            for w in range(w_total + 1):
                if w - weight_adj[j] >= 0:
                    dp[i + 1][j + 1][w] = dp[i][j][w - weight_adj[j]] + value[j]
                if dp[i + 1][j + 1][w] < dp[i + 1][j][w]:
                    dp[i + 1][j + 1][w] = dp[i + 1][j][w]
                if dp[i + 1][j + 1][w] < dp[i][j + 1][w]:
                    dp[i + 1][j + 1][w] = dp[i][j + 1][w]

    return max(dp[M][N][W - w0 * M], dp[M - 1][N][min(W - w0 * (M - 1), w_total)])


def main():
    N, W, *wv = map(int, read().split())
    weight = wv[::2]
    value = wv[1::2]

    if weight[0] < 500:
        ans = solve1(N, W, weight, value)
    else:
        ans = solve2(N, W, weight, value)

    print(ans)
    return


if __name__ == '__main__':
    main()

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] * 10010 for _ in range(N+1)]
minw = min(w)
for i in range(N):
    w[i] -= minw
    w[i] += 1
for i in range(N):
    for j in range(10000):
        dp[i+1][j] = dp[i][j]
        if j-w[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]]+v[i])

print(dp[N][min(W-minw,10000)])

Submission status: Runtime Error

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

dp = [[0] * 10010 for _ in range(N+1)]
minw = min(w)
for i in range(N):
    w[i] -= minw
    w[i] += 1
for i in range(N):
    for j in range(10000):
        dp[i+1][j] = dp[i][j]
        if j-w[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]]+v[i])
    
print(dp[N][W-minw])

Submission status: Runtime Error

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

dp = [[0] * 1010 for _ in range(N+1)]
minw = min(w)
for i in range(N):
    w[i] -= minw
    w[i] += 1
for i in range(N):
    for j in range(10000):
        dp[i+1][j] = dp[i][j]
        if j-w[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]]+v[i])
    
print(dp[N][W-minw])

Submission status: Runtime Error

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

dp = [[0] * 1010 for _ in range(N+1)]
minw = min(w)
for i in range(N):
    w[i] -= minw
    w[i] += 1
for i in range(N):
    for j in range(1000):
        dp[i+1][j] = dp[i][j]
        if j-w[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]]+v[i])
    
print(dp[N][W-minw])

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
a,v=map(int,input().split())
w0=[v]
w1=[]
w2=[]
w3=[]
for i in range(N-1):
    w,v=map(int,input().split())
    if w-a==0:
        w0.append(v)
    elif w-a==1:
        w1.append(v)
    elif w-a==2:
        w2.append(v)
    else:
        w3.appned(v)
w0=sorted(w0,reverse=True)
w1=sorted(w1,reverse=True)
w2=sorted(w2,reverse=True)
w3=sorted(w3,reverse=True)
ans=0
for i in range(max(len(w0)+1,1)):
    for j in range(max(len(w1)+1,1)):
        for k in range(max(len(w2)+1,1)):
            for l in range(max(len(w3)+1,1)):
                if a*i+(a+1)*j+(a+2)*k+(a+3)*l<=W:
                    lst=w0[:i]+w1[:j]+w2[:k]+w3[:l]
                    ans=max(sum(lst),ans)
print(ans)

Submission status: Runtime Error

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

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

print(max(lst))

Submission status: Runtime Error

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

for i in range(N):
    w,v=map(int,input().split())
    for i in range(W-w,-1,-1):
        if lst[i]!=-1:
            Value=lst[i]+v
            if Value>lst[i+w]:
                lst[i+w]=Value

print(max(lst))

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, W = getNM()
query = [getList() for i in range(N)]
wei = []
val = []
for i in range(N):
    w, v = query[i]
    wei.append(w)
    val.append(v)

wei_min = min(wei)
wei_max = max(wei)

def knapsack_1(N, limit, weight, value):
    dp = [[0] * (limit + 1) for i in range(N + 1)]
    dp[0][0] = 0

    for i in range(N):
        # wei_minごと飛ばす
        for k in range(0, limit + 1, wei_min):
            for j in range(min(0 + k, limit), min(500 + k, limit + 1, (wei_max * (i + 1)) + 1)):
                if weight[i] <= j:
                    dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])
                else:
                    dp[i + 1][j] = dp[i][j]
    return max(dp[N])

print(knapsack_1(N, W, wei, val))