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: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

# table = [[-1] * max(W + 1, (sum(w)))] * (N + 1)
table = []

def searchTable(item, weight):
    for i in range(len(table)):
        if table[i][0] == item and table[i][1] == weight:
            return True, table[i][2]
    return False, -1

def function(item, weight):
    # if table[item][weight] != -1:
    flag, data = searchTable(item, weight)
    if flag:
        return data
    if item == N:
        # print("item == N", item, weight)
        result = 0
    elif weight < w[item]:
        # print("weight < w[item]", item, weight)
        result = function(item + 1, weight)
    else:
        # print("check", item, weight)
        result = max(function(item + 1, weight - w[item]) + v[item], function(item + 1, weight))
        # result = max(function(item + 1, weight), function(item + 1, weight - w[item]) + v[item])

    # table[item][weight] = result
    table.append([item, weight, result])
    return result

print(function(0, W))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

for _ in range(N):
  tmp = input().split()
  w.append(int(tmp[0]))
  v.append(int(tmp[1]))

dp = []


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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np


if __name__ == "__main__":
	n, w = map(int, input().split())
	ws, vs = [], []
	for _ in range(n):
		w_, v_ = map(int, input().split())
		ws.append(w_)
		vs.append(v_)

	def rec(i, j, memo = [[-1 for _ in range(w+1)] for _ in range(n+1)]):


		if memo[i][j] != -1:
			return memo[i][j]

		result = 0
		if i == n:
			result = 0

		elif j < ws[i]:
			result = rec(i+1, j)

		else:
			result = max(
				rec(i+1, j),
				rec(i+1, j-ws[i]) + vs[i]
				)

		memo[i][j] = result

		#print(np.array(memo))
		#print('--------------------------')

		return memo[i][j]

	print(rec(0, w))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def generate():
    newGen = np.zeros(n)
    for p in range(pop):
        gen = np.random.rand(n)
        for i in range(n):
            if gen[i] > 0.5:
                gen[i] = 1
            else:
                gen[i] = 0
        newGen = np.vstack([newGen,gen])
    newGen = np.vsplit(newGen,[1])[1]
    return newGen

def evaluate(gen):
    sum = np.zeros(pop)
    for p in range(pop):
        for i in range(n):
            sum[p] += v[i][1] * gen[p][i]
    sum = sum.reshape(pop, 1)
    gen = np.hstack([gen, sum])
    return gen

def best(gen):
    best0 = gen[0]
    for p in range(1,pop):
        if best0[-1] < gen[p][-1]:
            best0 = gen[p]
    return best0

def select(b,p):
    parents = np.zeros(b.shape[1])
    for i in range(p):
        p1 = b[np.random.randint(0, b.shape[0] - 1)]
        p2 = b[np.random.randint(0, b.shape[0] - 1)]
        if p1[-1] < p2[-1]:
            parents = np.vstack([parents, p2])
        else:
            parents = np.vstack([parents, p1])
    return np.vsplit(parents,[1])[1]

def crossover(parents):
    parents = np.hsplit(parents, [-1])[0]
    newGen = np.zeros(parents.shape[1])
    for i in range(parents.shape[0] / 2):
        l = np.random.randint(1, parents.shape[1] - 1)
        p1_0, p1_1 = np.hsplit(parents[i * 2], [l])
        p2_0, p2_1 = np.hsplit(parents[i * 2 + 1], [l])
        c1 = np.hstack([p1_0, p2_1])
        c2 = np.hstack([p1_1, p2_0])
        newGen = np.vstack([newGen, c1])
        newGen = np.vstack([newGen, c2])
    return np.vsplit(newGen, [1])[1]

def mutation(newGen):
    for p in range(pop):
        w_sum = 0
        for i in range(n):
            w_sum += newGen[p][i] * v[i][0]
        if w_sum > w:
            ran = np.random.permutation(np.arange(n))
            while(w_sum > w):
                ran, q = np.hsplit(ran,[-1])
                if newGen[p][q] == 1:
                    w_sum -= newGen[p][q] * v[q][0]
                    newGen[p][q] = 0
    return newGen


pop = 10
n, w = map(int,raw_input().split())
v = []
N = 500
for i in range(n):
    v.append(map(int,raw_input().split()))

eval = evaluate(generate())
c = mutation(crossover(select(eval,pop)))
eval = evaluate(c)
be = best(eval)
for i in range(N):
    c = mutation(crossover(select(eval,pop)))
    eval = evaluate(c)
    if be[-1] < best(eval)[-1]:
        be = best(eval)
print int(be[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

import sys

def max_value(items, space):
    if len(items) == 1:
        if space >= items[0][0]:
            return items[0][1]
        else:
            return 0

    selected = 0
    if space >= items[0][0]:
        selected = items[0][1] + max_value(items[1:], space - items[0][0])
    not_selected = max_value(items[1:], space)

    return max(selected, not_selected)

def main(argv):
    line = sys.stdin.readline()
    while line:
        n, w = map(lambda x: int(x), line.split(" ", 2))

        items = []
        for i in range(n):
            weight, value = map(lambda x: int(x), raw_input().split(" ", 2))
            items.append((weight, value))

        print(max_value(items, w))

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def generate():
    newGen = np.zeros(n)
    for p in range(pop):
        gen = np.random.rand(n)
        for i in range(n):
            if gen[i] > 0.5:
                gen[i] = 1
            else:
                gen[i] = 0
        newGen = np.vstack([newGen,gen])
    newGen = np.vsplit(newGen,[1])[1]
    return newGen

def evaluate(gen):
    sum = np.zeros(pop)
    for p in range(pop):
        for i in range(n):
            sum[p] += v[i][1] * gen[p][i]
    sum = sum.reshape(pop, 1)
    gen = np.hstack([gen, sum])
    return gen

def best(gen):
    best0 = gen[0]
    for p in range(1,pop):
        if best0[-1] < gen[p][-1]:
            best0 = gen[p]
    return best0

def select(b,p):
    parents = np.zeros(b.shape[1])
    for i in range(p):
        p1 = b[np.random.randint(0, b.shape[0] - 1)]
        p2 = b[np.random.randint(0, b.shape[0] - 1)]
        if p1[-1] < p2[-1]:
            parents = np.vstack([parents, p2])
        else:
            parents = np.vstack([parents, p1])
    return np.vsplit(parents,[1])[1]

def crossover(parents):
    parents = np.hsplit(parents, [-1])[0]
    newGen = np.zeros(parents.shape[1])
    for i in range(parents.shape[0] / 2):
        l = np.random.randint(1, parents.shape[1] - 1)
        p1_0, p1_1 = np.hsplit(parents[i * 2], [l])
        p2_0, p2_1 = np.hsplit(parents[i * 2 + 1], [l])
        c1 = np.hstack([p1_0, p2_1])
        c2 = np.hstack([p1_1, p2_0])
        newGen = np.vstack([newGen, c1])
        newGen = np.vstack([newGen, c2])
    return np.vsplit(newGen, [1])[1]

def mutation(newGen):
    for p in range(pop):
        w_sum = 0
        for i in range(n):
            w_sum += newGen[p][i] * v[i][0]
        if w_sum > w:
            ran = np.random.permutation(np.arange(n))
            while(w_sum > w):
                ran, q = np.hsplit(ran,[-1])
                if newGen[p][q] == 1:
                    w_sum -= newGen[p][q] * v[q][0]
                    newGen[p][q] = 0
    return newGen


pop = 10
n, w = map(int,raw_input().split())
v = []
N = 1000
for i in range(n):
    v.append(map(int,raw_input().split()))

eval = evaluate(generate())
c = mutation(crossover(select(eval,pop)))
eval = evaluate(c)
be = best(eval)
for i in range(N):
    c = mutation(crossover(select(eval,pop)))
    eval = evaluate(c)
    if be[-1] < best(eval)[-1]:
        be = best(eval)
print int(be[-1])

Submission status: Time Limit Exceeded

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

for _ in range(N):
  tmp = input().split()
  w.append(int(tmp[0]))
  v.append(int(tmp[1]))

dp = []

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



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

Submission status: Time Limit Exceeded

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

for _ in range(N):
  tmp = input().split()
  w.append(int(tmp[0]))
  v.append(int(tmp[1]))

dp = []

for _ in range(W+1):
  dp.append([])


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



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

Submission status: Time Limit Exceeded

Solution code:
# 参考サイト: http://futurismo.biz/archives/5436

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

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

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

for i in range(N - 1, -1, -1):
    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: Time Limit Exceeded

Solution code:
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 add(i, w_max):
    if i == N:
        return 0;
    if w_max < items[i]['w']:
        return add(i+1, w_max)

    return max(
        add(i+1, w_max),
        add(i+1, w_max - items[i]['w']) + items[i]['v']
    )

print(add(0, W))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

INF = 10**9+7

stdin = sys.stdin
def na(): return map(int, stdin.readline().split())
def ns(): return stdin.readline().strip()
def nsl(): return list(stdin.readline().strip())
def ni(): return int(stdin.readline())
def nil(): return list(map(int, stdin.readline().split()))

N, W = nil()
w = []
v = []
for i in range(N):
    a, b = nil()
    w.append(a)
    v.append(b)

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

def rec(i, j):

    if dp[i][j] != -1:
        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


ans = rec(0, W)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

INF = 10**9+7

stdin = sys.stdin
def na(): return map(int, stdin.readline().split())
def ns(): return stdin.readline().strip()
def nsl(): return list(stdin.readline().strip())
def ni(): return int(stdin.readline())
def nil(): return list(map(int, stdin.readline().split()))

N, W = nil()
w = []
v = []
for i in range(N):
    a, b = nil()
    w.append(a)
    v.append(b)

def rec(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])

    return res


ans = rec(0, W)

print(ans)

Submission status: Time Limit Exceeded

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

w = []
v = []

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



def d(i, j):
    if i == 0:
        if w[0] <= j:
            return v[0]
        else:
            return 0
    else:
        if j >= w[i]:
            return max(d(i-1, j), d(i-1, j-w[i]) + v[i])
        else:
            return d(i-1, j)

print(d(N - 1, W))

Submission status: Time Limit Exceeded

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

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



def dfs(k, w, v):
    if k == N:
        return v

    this = item[k]
    if w + this[0] > W:
        return dfs(k + 1, w, v)


    new_w = w + this[0]
    new_v = v + this[1]

    return max(dfs(k + 1, w, v), dfs(k + 1, new_w, new_v))


print(dfs(0, 0, 0))

Submission status: Time Limit Exceeded

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

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

for i in range(N - 1, -1, -1):
    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: Time Limit Exceeded

Solution code:
def maxvalue(p, i, w):
    if i == len(p) - 1:
        if p[i][0] > w:
            return 0
        else:
            return p[i][1]
    if w >= p[i][0]:
        return max(maxvalue(p, i+1, w-p[i][0]) + p[i][1], maxvalue(p, i+1, w))
    else:
        return maxvalue(p, i+1, w)

N, W = map(int, input().split())
p = []
for i in range(N):
    w, v = map(int, input().split())
    p.append((w, v))
    
print(maxvalue(p, 0, W))

Submission status: Memory Limit Exceeded

Solution code:
N, W = map(int, input().split())
w0 = 0
Items = []
for _ in range(N):
    w, v = map(int, input().split())
    if _ == 0:
        w0 = w
        w = 0
    else:
        w -= w0
    Items.append((w, v))
# i個目までを見たときに、重さはk, j個使用
DP = [[[0] * (N * 5) for _ in range(N * 5)] for __ in range(N+1)]

for i, (w, v) in enumerate(Items, 1):
    for j in range(1, N * 5):
        if i < j:
            break
        for k in range(N * 5):
            if k < w:
                DP[i][j][k] = DP[i-1][j][k]
            else:
                DP[i][j][k] = max(DP[i-1][j][k], DP[i-1][j-1][k-w] + v)

ans = 0
for j, value in enumerate(DP[N]):
    for k, v in enumerate(value):
        if j * w0 + k <= W:
            ans = max(ans, v)
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,w]=i2()
a=[]
dp=[[-1 for j in range(200000)]for i in range(n+1)]
dp[0][0]=0
for i in range(n):
 a.append(i2())
b=a[0][0]
c=0
for i in range(1,n+1):
 for j in range(200000):
   dp[i][j]=max(dp[i][j],dp[i-1][j])
   k1=j//1000
   k2=j%1000
   if k1*b+k2<=w and j-1000-a[i-1][0]+b>=0 and dp[i-1][j-1000-a[i-1][0]+b]>=0:
     if dp[i][j]<dp[i-1][j-1000-a[i-1][0]+b]+a[i-1][1]:
        dp[i][j]=dp[i-1][j-1000-a[i-1][0]+b]+a[i-1][1]

   if c<dp[i][j]:
     c=dp[i][j]
     
print(c)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
import sys
n,W = ma()
wm=3*(n-1)
dp=[[[0]*(wm+1) for j in range(n+1)] for j in range(n+1) ] #dp[i][j][w] iまで見てj個使った時に重さwとなる場合のmaxのv
wv=[]
for i in range(n):
    w,v=ma()
    if i==0:
        wv.append((0,v))
        w0=w
    else:
        wv.append((w-w0,v))

for i in range(n):
    w,v = wv[i]
    for j in range(1,i+2):
        #print(i,j)
        for ww in range(wm+1):
            dp[i][j][ww]=dp[i-1][j][ww]
            if ww-w>=0:
                dp[i][j][ww]=max(dp[i-1][j-1][ww-w]+v,dp[i][j][ww])
ans=0
for j in range(n+1):
    for w in range(wm+1):
        if j*w0 + w<=W:
            ans=max(ans,dp[n-1][j][w])
print(ans)
# print(wv)
# for i in range(n):
#     print(dp[i])
#     print()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

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


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

    w0 = weight[0]
    items = [[] for _ in range(4)]
    for w, v in zip(weight, value):
        items[w - w0].append(v)

    for i in range(4):
        items[i].sort(reverse=True)

    csums = [0] * 4
    for i in range(4):
        csums[i] = [0]
        csums[i].extend(accumulate(items[i]))

    def rec(i, w, v):
        if i == 4:
            return v
        ans = 0
        w_next = w
        for j in range(len(csums[i])):
            if w_next > W:
                break
            ans = max(ans, rec(i + 1, w_next, v + csums[i][j]))
            w_next += w0 + i

        return ans

    print(rec(0, 0, 0))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

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


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

    w_min = min(weight)
    items = [[] for _ in range(4)]
    for w, v in zip(weight, value):
        items[w - w_min].append(v)

    for i in range(4):
        items[i].sort(reverse=True)

    csums = [0] * 4
    for i in range(4):
        csums[i] = [0]
        csums[i].extend(accumulate(items[i]))

    def rec(i, w, v):
        if i == 4:
            if w <= W:
                return v
            else:
                return -1
        ans = 0
        for j in range(len(csums[i])):
            w_next = w + (w_min + i) * j
            if w_next > W:
                break
            ans = max(ans, rec(i + 1, w_next, v + csums[i][j]))

        return ans

    print(rec(0, 0, 0))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

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


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

    w_min = min(weight)
    items = [[] for _ in range(4)]
    for w, v in zip(weight, value):
        items[w - w_min].append(v)

    for i in range(4):
        items[i].sort(reverse=True)

    csums = [0] * 4
    for i in range(4):
        csums[i] = [0]
        csums[i].extend(accumulate(items[i]))

    def rec(i, w, v):
        if i == 4:
            if w <= W:
                return v
            else:
                return -1
        ans = 0
        for j in range(len(csums[i])):
            ans = max(ans, rec(i + 1, w + (w_min + i) * j, v + csums[i][j]))

        return ans

    print(rec(0, 0, 0))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

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


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

    w_min = min(weight)
    items = [[] for _ in range(4)]
    for w, v in zip(weight, value):
        items[w - w_min].append(v)

    for i in range(4):
        items[i].sort(reverse=True)

    csums = [0] * 4
    for i in range(4):
        csums[i] = [0]
        csums[i].extend(accumulate(items[i]))

    def rec(i, vec):
        if i == 4:
            ans = 0
            w_total = 0
            for j in range(4):
                w_total += (w_min + j) * vec[j]
            if w_total > W:
                return -1
            for j in range(4):
                ans += csums[j][vec[j]]
            return ans
        ans = 0
        for j in range(len(csums[i])):
            vec.append(j)
            ans = max(ans, rec(i + 1, vec))
            vec.pop()
        return ans

    print(rec(0, []))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
Items = [tuple(map(int, input().split())) for _ in range(N)]
from collections import defaultdict as dd
Bag = dd(lambda:0)
Bag[0] = 0
for w,v in Items:
    temp = [(key+w,Bag[key]+v) for key in Bag if key + w <= W]
    for key,value in temp:
        Bag[key] = max(Bag[key],value)
ans = max(Bag.values())
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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] = 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 = 0
            if i != 0:
              t += vs[0][i - 1]
            if j != 0:
              t += vs[1][j - 1]
            if k != 0:
              t += vs[2][k - 1]
            for l in range(len(vs[3]) + 1):
                d = c - (w1 + 3) * l
                if d < 0:
                    break
                if l == 0:
                    result = max(result, t)
                else:
                    result = max(result, t + vs[3][l -1])
print(result)

Submission status: Accepted

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

dp = [[[-10**10]*(320) for j in range(100)] for i in range(N)]
#dp[i個までで][j個もって][余り部分kの重さ]の時の価値最大値

dp[0][0][0] = 0
dp[0][1][0] = wv[0][1]
for i in range(1,N):
    for j in range(100):
        for k in range(320):
            dp[i][j][k]=dp[i-1][j][k]#持たない
            if j-1>=0 and k+wv[0][0]-wv[i][0]>=0:#持つ
                dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k+wv[0][0]-wv[i][0]]+wv[i][1])
    
ans = 0
for j in range(100):
    for k in range(320):
        if j*wv[0][0]+k <= W:
            ans = max(ans,dp[N-1][j][k])


print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w0 = 0
Items = []
for _ in range(N):
    w, v = map(int, input().split())
    if _ == 0:
        w0 = w
        w = 0
    else:
        w -= w0
    Items.append((w, v))
# i個目までを見たときに、重さはk, j個使用
DP = [[[0] * (N * 4) for _ in range(N * 4)] for __ in range(N+1)]

for i, (w, v) in enumerate(Items, 1):
    for j in range(1, N * 4):
        if i < j:
            break
        for k in range(N * 4):
            if k < w:
                DP[i][j][k] = DP[i-1][j][k]
            else:
                DP[i][j][k] = max(DP[i-1][j][k], DP[i-1][j-1][k-w] + v)

ans = 0
for j, value in enumerate(DP[N]):
    for k, v in enumerate(value):
        if j * w0 + k <= W:
            ans = max(ans, v)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
N, W = map(int, input().split())
wv_dict = defaultdict(list)
for i in range(N):
    w, v = map(int, input().split())
    wv_dict[w] += [v]
sorted_w = sorted(wv_dict.keys())
w0 = sorted_w[0]
w_list = [w0 + i for i in range(4)]
for key in w_list:
    sorted_v = sorted(wv_dict[key], reverse=True)
    for i in range(len(sorted_v)-1):
        sorted_v[i+1] += sorted_v[i]
    wv_dict[key] = [0] + sorted_v
w0, w1, w2, w3 = [w0 + i for i in range(4)]
ans = 0
for c0 in range(len(wv_dict[w0])):
    for c1 in range(len(wv_dict[w0+1])):
        for c2 in range(len(wv_dict[w0+2])):
            for c3 in range(len(wv_dict[w0+3])):
                if w0 * c0 + w1 * c1 + \
                    w2 * c2 + w3 * c3 <= W:
                    v = wv_dict[w0][c0] + wv_dict[w1][c1] + \
                        wv_dict[w2][c2] + wv_dict[w3][c3]
                    ans = max(ans, v)

print(ans)

Submission status: Accepted

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]

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

# dp[i][j] = i個選んで重さの余りがjの時の、価値の最大値
dp = [[0] * (3*n+1) 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+1):
        if base * i + j <= weight and ans < dp[i][j]:
            ans = dp[i][j]

print(ans)

Submission status: Accepted

Solution code:
#DP[i][j][k] = (i番目まで、j個選ぶ、有効重さの和kのときの最大得点)

N, W = map(int, input().split())
INF = 10**13
DP = [[[-INF for _ in range(3*N+1)] for _ in range(N+1)] for _ in range(N+1)]
w0, v = map(int, input().split())
DP[1][0][0] = 0
DP[1][1][0] = v

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

#print(w0)
#print(DP)
#print([max(DP[N][j]) + w0*j for j in range(N+1)])
#print(max([max(DP[N][j]) + w0*j for j in range(N+1)]))
ans = max([max([DP[N][j][k] for k in range(min(3*N,W-w0*j)+1)]) if W-w0*j >= 0 else -INF for j in range(N+1)])
print(ans)

Submission status: Accepted

Solution code:
n, W = map(int, input().split())
wv = []
for i in range(n):
    wv.append(list(map(int, input().split())))
num = wv[0][0]
dp = [[-float("inf") for i in range(3 * (n - 1) + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    w, v = wv[i][0], wv[i][1]
    w -= num
    for j in range(n - 1, -1, -1):
        for k in range(3 * (n - 1) + 1 - w):
            dp[j + 1][k + w] = max(dp[j + 1][k + w], dp[j][k] + v)
ans = 0
for i in range(3 * (n - 1) + 1):
    for j in range(n + 1):
        if j * num + i <= W:
            ans = max(ans, dp[j][i])
print(ans)

Submission status: Accepted

Solution code:
from collections import *
N,W = map(int,input().split())
dp = defaultdict(int)
dp[0] = 0

for n in range(N):
  w1,v1 = map(int,input().split())
  for w2,v2 in dp.copy().items():
    if w1+w2<=W:
      dp[w1+w2] = max(dp[w1+w2],v1+v2)

print(max(dp.values()))

Submission status: Accepted

Solution code:
from collections import *
N,W = map(int,input().split())
dp = defaultdict(int)
dp[0] = 0

for n in range(N):
  w,v = map(int,input().split())
  for k,b in dp.copy().items():
    if k+w<=W:
      dp[k+w] = max(dp[k+w],b+v)

print(max(dp.values()))

Submission status: Accepted

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

n, wei = map(int,readline().split())

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

w1,w2,w3,w4 = [],[],[],[]
for i in range(n):
    if w[i] == w[0]: w1.append(v[i])
    if w[i] == w[0] + 1: w2.append(v[i])
    if w[i] == w[0] + 2: w3.append(v[i])
    if w[i] == w[0] + 3: w4.append(v[i])

w1 = [0] + list(accumulate(sorted(w1, reverse=True)))
w2 = [0] + list(accumulate(sorted(w2, reverse=True)))
w3 = [0] + list(accumulate(sorted(w3, reverse=True)))
w4 = [0] + list(accumulate(sorted(w4, reverse=True)))

ans = 0
for i in range(len(w1)):
    for j in range(len(w2)):
        for k in range(len(w3)):
            for l in range(len(w4)):
                vsum = w1[i] + w2[j] + w3[k] + w4[l];
                wsum = w[0]*i + (w[0]+1)*j + (w[0]+2)*k + (w[0]+3)*l;
                if wsum <= wei: ans = max(ans,vsum)

print(ans)