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

Solution code:
N, W = map(int, input().split())
items = []
for _ in range(N):
    w, v = map(int, input().split())
    items.append({"w": w, "v": v})

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


for i in range(N):
    item_w = items[i]["w"]
    item_v = items[i]["v"]
    for w in range(W + 1):
        if w >= item_w:
            dp[i + 1][w] = max(dp[i][w - item_w] + item_v, dp[i][w])
        else:
            dp[i + 1][w] = dp[i][w]


print(dp[N][W])

Submission status: Runtime Error

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

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


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


print(dp[N][W])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
items = []
for _ in range(N):
    w, v = map(int, input().split())
    items.append({"w": w, "v": v})

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


for i in range(1, N + 1):
    item_w = items[i - 1]["w"]
    item_v = items[i - 1]["v"]
    for w in range(W + 1):
        if w >= item_w:
            dp[i][w] = max(dp[i - 1][w - item_w] + item_v, dp[i - 1][w])
        else:
            dp[i][w] = dp[i - 1][w]


print(dp[N][W])

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
wv=[[int(j) for j in input().split()] for _ in range(N) ]
w0=wv[0][0]
w1=w0+1
w2=w1+1 
w3=w2+1
wv=sorted(wv,key=lambda x:x[1],reverse=True)
wv=sorted(wv)

ans=0
from bisect import bisect_left as bll
for e1 in range(0,W//w0+1):
  l2=W-w0*e1
  for e2 in range(0,l2//(w0+1)+1):
    l3=l2-(w0+1)*e2
    for e3 in range(0,l3//(w0+2)+1):
      l4=l3- (w0+2)*e3
      e4 =l4//(w0+3)    
      tmp=0
      i1=bll(wv, (w0,inf))
      i2=bll(wv, (w1,inf))
      i3=bll(wv, (w2,inf))
      i4=bll(wv, (w3,inf))
      tmp+=sum(wv[i1:i1+e1])  \
         +sum(wv[i2:i2+e2])  \
         +sum(wv[i3:i3+e3])  \
        +sum(wv[i4:i4+e4])
      ans=max(ans,tmp)
      
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, W = map(int, input().split())
first_item = list(map(int, input().split()))
basew = first_item[0]
w0 = []
w1 = []
w2 = []
w3 = []
heapq.heappush(w0, first_item[1])
for _ in range(N-1):
    w, v = map(int, input().split())
    w -= basew
    if w == 0:
        heapq.heappush(w0, v)
    elif w == 1:
        heapq.heappush(w1, v)
    elif w == 2:
        heapq.heappush(w2, v)
    elif w == 3:
        heapq.heappush(w3, v)

w0_acc = [0]+list(accumulate(reversed(w0)))
w1_acc = [0]+list(accumulate(reversed(w1)))
w2_acc = [0]+list(accumulate(reversed(w2)))
w3_acc = [0]+list(accumulate(reversed(w3)))
print("acc-0", w0_acc)
print("acc-1", w1_acc)
print("acc-2", w2_acc)
print("acc-3", w3_acc)
v = 0
for i0 in range(N+1):
    for i1 in range(N+1):
        for i2 in range(N+1):
            for i3 in range(N+1):
                if basew*(i0+i1+i2+i3)+3*i3 + 2*i2 + i1 > W:
                    break
                else:
                    v = max(v, w0_acc[i0]+w1_acc[i1]+w2_acc[i2]+w3_acc[i3])
print(v)

Submission status: Runtime Error

Solution code:
N, W = (int(i) for i in input().split())
w = [0]*N
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(j) for j in input().split())
w0 = w[0]
wh = [a - w0 for a in w]
dp = [[[-1]*(N+1) for i in range(3*N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
  for j in range(3*N+1):
    for k in range(N+1):
      if dp[i][j][k] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0 and dp[i][j-wh[i]][k-1] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for k in range(N+1):
  if w0*k <= W:
    Wk = W - w0*k
    ans = 0
    for j in range(Wk+1):
      ans = max(dp[N][j][k], ans)
    res = max(res, ans)
print(res)

Submission status: Runtime Error

Solution code:
N, W = (int(i) for i in input().split())
w = [0]*N
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(j) for j in input().split())
w0 = w[0]
wh = [a - w0 for a in w]
dp = [[[-1]*(N+1) for i in range(3*N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
  for j in range(3*N+1):
    for k in range(N+1):
      if dp[i][j][k] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0 and dp[i][j-wh[i]][k-1] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for j in range(3*N+1):
  for k in range(N+1)
  	if j + w0*k <= W:
      res = max(dp[N][j][k], res)
print(res)

Submission status: Runtime Error

Solution code:
N, W = (int(i) for i in input().split())
w = [0]*N
w0 = w[0]
wh = [a - w0 for a in W]
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(i) for i in input().split())
dp = [[[0]*(N+1) for i in range(3N+1)] for j in range(N+1)]
for i in range(N):
  for j in range(3N+1):
    for k in range(N+1):
      dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for k in range(N+1):
  if w0*k <= W <= (w0+3)*k:
    Wk = W - w0*k
    ans = 0
    for j in range(Wk+1):
      ans = max(dp[N][j][k], ans)
    res = max(res, ans)
print(res)

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

items = []
for _ in range(N):
    a, b = map(int, input().split())
    items.append([a, b])

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

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

print(dp[0][W])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, W] =  [long(input_raw[0]), long(input_raw[1])]
    v = []
    w = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [wi, vi] =  [long(input_raw[0]), long(input_raw[1])]
        v.append(vi)
        w.append(wi)

    W_ = long(N * 100)
    dp = [[0L for j in range((W_) + 1)] for i in range(N + 1)]

    for i in range(N):
        for j in range(W_ + 1):
            k = max(0, ((j + w[0] - 1) - w[i]) - w[0] + 1)
            #print k, j, w[i]
            if (j + w[0] - 1) - w[i]  < 0:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][k] + v[i])


    print dp[N][max(0, W - w[0] + 1)]


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, W] =  [long(input_raw[0]), long(input_raw[1])]
    v = []
    w = []
    for i in range(N):
        input_raw = read_func().strip().split()
        [wi, vi] =  [long(input_raw[0]), long(input_raw[1])]
        v.append(vi)
        w.append(wi)

    W_ = long(N * 4)
    dp = [[0L for j in range((W_) + 1)] for i in range(N + 1)]

    for i in range(N):
        for j in range(W_ + 1):
            k = max(0, ((j + w[0] - 1) - w[i]) - w[0] + 1)
            #print k, j, w[i]
            if (j + w[0] - 1) - w[i]  < 0:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][k] + v[i])


    print dp[N][max(0, W - w[0] + 1)]


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

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

dp = [[0] * (W + 1) for i in range(N + 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:


import numpy as np

temp = [int(i) for i in input().split()]

N = temp[0]
maxWeight = temp[1]


# matrix = [[0 for i in range(maxWeight+1)] for j in range(N)]


# for i in range(N):
# 	matrix[i][0] = 0

value = []
weight = []


matrix = np.zeros((N,maxWeight+1), dtype=np.int)

# items are stored as tuples (w, v) 
for i in range(N):
	x = [int(i) for i in input().split()]
	if x[0] <= maxWeight:
		weight.append((x[1], x[0]))

weight.sort()
weight.reverse()

for item in range(N):

	minStart = min(weight)[1]

	for totalWeight in range(minStart, maxWeight+1):		# we start from weight 0
		
		currentWeight = weight[item][1]

		if item == 0:
			if totalWeight < currentWeight:
				matrix[item][totalWeight] = 0
			
			else:
				matrix[item][totalWeight] = weight[item][0]


		else:
			if totalWeight < currentWeight:
				matrix[item][totalWeight] = matrix[item-1][totalWeight]

			else:
				pos1 = weight[item][0] + matrix[item-1][totalWeight-weight[item][1]]
				pos2 = matrix[item-1][totalWeight]
				matrix[item][totalWeight] = max(pos1, pos2)

# for i in matrix:
# 	print(i)

print(matrix[N-1][maxWeight])

Submission status: Runtime Error

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

N, W = map(int, raw_input().split(' '))
w, v = [], []
for i in range(N):
    _w, _v = map(int, raw_input().split(' '))
    w.append(_w)
    v.append(_v)

toriuru_w = [0]
for p in range(N):
    toriuru_w.extend([w[0]*(p+1) + i for i in range(3*p+4)])
toriuru_w = list(set(toriuru_w))
toriuru_w = filter(lambda x: x <= W, toriuru_w)

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

#toriuru_w = [0, 5, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 21]
def floor_like(n):
    min_, max_ = 0, len(toriuru_w)
    while min_ != max_:
        if n <= toriuru_w[(min_ + max_) / 2]:
            max_ = (min_ + max_) / 2
        else:
            min_ = (min_ + max_) / 2 + 1

    if min_ >= len(toriuru_w):
        return min_

    if toriuru_w[min_] == n:
        return min_
    else:
        return max(0, min_ - 1)


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


print dp[-1][-1]

Submission status: Runtime Error

Solution code:
import itertools
a = list(map(int, input().split()))
N,W = a[0],a[1]
tup =zip(a[2::2], a[3::2])
dic = {}
for val in tup:
    if val[0] in dic.keys():
        if val[1] >= dic[val[0]]:
            dic.update({val[0]:val[1]})
    else:
        dic.update({val[0]:val[1]})

t = max([max([sum(map(lambda x: dic[x], element)) for element in itertools.combinations(dic.keys(),i) if sum(element)<= W]) for i in range(len(dic.keys()))])
print(t)

Submission status: Runtime Error

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


def simple_dp():
    offset = w[0]
    maximum = min(100 * (w[0] + 3), W + 1)
    dp = [[-1] * (maximum + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        if w[i] <= W:
            dp[i + 1][w[i]] = max(dp[i + 1][w[i]], dp[i][0] + v[i])
        dp[i + 1][0] = dp[i][0]

        for jj in list(range(w[0], maximum + 1)):
            j = jj - offset + 1
            if dp[i][j] < 0:
                continue
            if jj + w[i] <= W + 1:
                dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i])
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        # print(list(zip(*dp)))

    ans = 0
    for i in range(W + 1):
        ans = max(ans, dp[N][i])
    return ans

print(simple_dp())

Submission status: Runtime Error

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


def simple_dp():
    dp = [[-1] * (W + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in [0] + list(range(w[0], min(100 * (w[0] + 3), W + 1))):
            if dp[i][j] < 0:
                continue
            if j + w[i] <= W:
                dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i])
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

    ans = 0
    for i in range(W + 1):
        ans = max(ans, dp[N][i])
    return ans

print(simple_dp())

Submission status: Runtime Error

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

def knapsack2(items, W):
    N = len(items)
    C = np.zeros((N+1, W+1))
    for i in range(N+1)[1:]:
        v, w = items[i-1]
        for j in range(W+1)[1:]:
            if j < w:
                C[i][j] = C[i-1][j]
            else:
                C[i][j] = max(C[i-1][j-w]+v, C[i-1][j])

    return long(C[N][W])


def input_str(row):
    res = []
    for _ in xrange(row):
        res.append(raw_input().split())
    return res


N, W = [int(i) for i in raw_input().split()]
wvlist = input_str(N)
items = [(int(v), int(w)) for w, v in wvlist]
print knapsack2(items, W)

Submission status: Runtime Error

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

def knapsack2(items, W):
    N = len(items)
    C = np.zeros((N+1, W+1))
    for i in range(N+1)[1:]:
        v, w = items[i-1]
        for j in range(W+1)[1:]:
            if j < w:
                C[i][j] = C[i-1][j]
            else:
                C[i][j] = max(C[i-1][j-w]+v, C[i-1][j])

    return int(C[N][W])


def input_str(row):
    res = []
    for _ in xrange(row):
        res.append(raw_input().split())
    return res


N, W = [int(i) for i in raw_input().split()]
wvlist = input_str(N)
items = [(int(v), int(w)) for w, v in wvlist]
print knapsack2(items, W)

Submission status: Runtime Error

Solution code:
#-*- coding: utf-8 -*-
def knapsack2(items, W):
    N = len(items)
    C = [[0 for _i in xrange(W+1)] for _j in xrange(N+1)]
    for i in range(N+1)[1:]:
        v, w = items[i-1]
        for j in range(W+1)[1:]:
            if j < w:
                C[i][j] = C[i-1][j]
            else:
                C[i][j] = max(C[i-1][j-w]+v, C[i-1][j])

    return C[-1][-1]

N, W = [int(i) for i in raw_input().split()]
wvlist = input_str(N)
items = [(int(v), int(w)) for w, v in wvlist]
print knapsack2(items, W)

Submission status: Runtime Error

Solution code:

import bisect

if 1:
    N,W = map(int, input().split(' '))
    w,v = [],[]
    for i in range(N):
        w_,v_ = map(int, input().split(' '))
        w.append(w_)
        v.append(v_)
else:
    N,W = 4,6
    w = [2,3,4,3]
    v = [1,4,10,4]

w0 = w[0]

idxs = set()
for i in range(N):
    for j in range(3*i+1):
        if i*w0+j <= W:
            idxs.add(i*w0+j)
idxs = list(idxs) 
idx_dict = {idx:i for i,idx in enumerate(idxs)}

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

for i in range(N):
    for j in range(len(idxs)):
        if idxs[j] < w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            k = bisect.bisect_left(idxs, idxs[j]-w[i])
            dp[i+1][j] = max([dp[i][j],dp[i][idx_dict[idxs[k]]]+v[i]])
                
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]

m = {}
def update(W, wi, vi):
        if wi > W:
                return
        global m
        ks = m.keys()
        a = set()
        for wj in ks:
                wk = wj + wi
                if wk <= W:
                        vk = m[wj] + vi
                        if wk not in m or m[wk] < vk:
                                m[wk] = vk
                                a.add(wk)
        if wi not in m or m[wi] < vi:
                m[wi] = vi
                a.add(wi)
        for wj in a:
                for wk in ks:
                        if wk in m and wk > wj and m[wk] <= m[wj]:
                                del(m[wk])
                                break

def calc(W, w, v):
        global m
        m = {}
        for i in range(len(w)):
                update(W, w[i], v[i])
        print max(m.values() + [0])

N, W = rdi()
w = []
v = []
for i in range(N):
        wi, vi = rdi()
        w.append(wi)
        v.append(vi)
calc(W, w, v)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import array, bisect, collections, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def solve(N, W, w, v):
    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 < 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])
    
    ans = dp[0][W]
    return ans


def main():
    N, W = ILI()
    w, v = [], []
    for __ in range(N):
        x, y = ILI()
        w.append(x)
        v.append(y)
    print(solve(N, W, w, v))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N,W=map(int,raw_input().split())
w=[0]*N
v=[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,raw_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: Runtime Error

Solution code:
#coding: utf-8

N, W = map(int, raw_input().split())
items = []
for i in range(N):
    items.append(map(int, raw_input().split())) #weight, value

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

def proc(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
    if i == N:
        res = 0
    elif j < items[i][0]:
        res = proc(i + 1, j)
    else: 
        res = max(proc(i + 1, j), proc(i + 1, j - items[i][0]) + items[i][1])
        dp[i][j] = res 
    return res 

print(proc(0, W))

Submission status: Runtime Error

Solution code:
#coding: utf-8                                                                                                                                                

N, W = map(int, raw_input().split())
items = []
for i in range(N):
    items.append(map(int, raw_input().split())) #weight, value                                                                                                

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

print(dp[0][W])