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.

Solution (Python):

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):
    memo = collections.defaultdict(int)
    memo[0] = 0
    for w, v in w_v:
        for w_memo, v_memo in sorted(list(memo.items()), key=lambda x: -x[0]):
            if w + w_memo > W:
                continue
            if memo[w + w_memo] < v_memo + v:
                memo[w + w_memo] = v_memo + v

    return max(memo.values())


def main():
    N, W = ILI()
    w_v = IAI(N)
    print(solve(N, W, w_v))


if __name__ == "__main__":
    main()

Solution (Python):

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+1):
    for j in range(3*i+1):
        if i*w0+j <= W:
            idxs.add(i*w0+j)
idxs = sorted(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:
            try:
                dp[i+1][j] = max([dp[i][j],dp[i][idx_dict[idxs[j]-w[i]]]+v[i]])
            except:
                dp[i+1][j] = dp[i][j]
        
print(max([max(dp_) for dp_ in dp]))

Solution (Python):
import collections
import functools

class memoized(object):
    def __init__(self, func):
       self.func = func
       self.cache = {}

    def __call__(self, *args):
       if not isinstance(args, collections.Hashable):
          return self.func(*args)

       if args in self.cache:
          return self.cache[args]

       else:
          value = self.func(*args)
          self.cache[args] = value
          return value

    def __repr__(self):
       return self.func.__doc__

    def __get__(self, obj, objtype):
       return functools.partial(self.__call__, obj)

def knapsack(items, maxweight):
    @memoized
    def bestvalue(i, j):
        if i == 0: return 0
        value, weight = items[i - 1]
        if weight > j:
            return bestvalue(i - 1, j)
        else:
            return max(bestvalue(i - 1, j),
                       bestvalue(i - 1, j - weight) + value)

    j = maxweight
    result = []
    for i in xrange(len(items), 0, -1):
        if bestvalue(i, j) != bestvalue(i - 1, j):
            result.append(items[i - 1])
            j -= items[i - 1][1]
    result.reverse()
    return bestvalue(len(items), maxweight), result

def input_str(row):
    res = []
    for _ in range(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 knapsack(items, W)[0]

Solution (Python):
N, W = map(int, input().split())
ws = []
vs = []

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

w1 = ws[0]
s = 0

for i in range(N):
	ws[i] -= w1
	s += ws[i]

dp = [[[0]*(s+1) for i in range(N+1)] for k in range(N)]
for k in range(N):
	if (k+1)*w1 > W:
		break
	for i in range(1,N+1):
		for j in range(s+1):
			if j >= ws[i-1]:
				dp[k][i][j] = max(dp[k-1][i-1][j-ws[i-1]]+vs[i-1], dp[k][i-1][j])
			else:
				dp[k][i][j] = max(dp[k][i][j], dp[k][i-1][j])
			if j > 0:
				dp[k][i][j] = max(dp[k][i][j], dp[k][i][j-1])
ans = 0
for k in range(N):
	if W < (k+1)*w1:
		break
	ans = max(ans, dp[k][N][min(W-(k+1)*w1, s)])
print(ans)
from sys import stderr
print(dp, file=stderr)

Solution (Python):
N, W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w, v = map(int, input().split())
    ws.append(w)
    vs.append(v)

vss = [[], [], [], []]

for i in range(N):
    ind = ws[i] - ws[0]
    vss[ind].append(vs[i])

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

dic = {}




def rec(vss, tmp_W, tmp_V, select_S):
    
    for i in range(4):
        if len(vss[i]) == 0:
            continue
        new_tmp_W = tmp_W + ws[0] + i
        if new_tmp_W > W:
            continue
        new_tmp_V = tmp_V + vss[i][0]
        new_vss = list(vss)
        new_vss[i] = new_vss[i][1:]

        new_select_S = [select_S[j] for j in range(4)]
        new_select_S[i] += 1
        new_select_S = tuple(new_select_S)
        if new_select_S in dic:
            continue

        dic[new_select_S] = new_tmp_V
        rec(new_vss, new_tmp_W, new_tmp_V, new_select_S)


rec(vss, 0, 0, (0, 0, 0, 0))
ans = sorted(list(dic.values()), reverse=True)
if len(ans) == 0:
    print(0)
else:
    print(ans[0])

Solution (Python):

import numpy as np
N, W = map(int, input().split())
v_list_0 = []
v_list_1 = []
v_list_2 = []
v_list_3 = []

w0, v0 = map(int, input().split())
v_list_0.append(v0)

for i in range(1, N):
    w, v = map(int, input().split())
    if w == w0:
        v_list_0.append(v)
    elif w == w0+1:
        v_list_1.append(v)
    elif w == w0+2:
        v_list_2.append(v)
    else:
        v_list_3.append(v)


vn0 = np.cumsum([0] + sorted(v_list_0, reverse=True))
vn1 = np.cumsum([0] + sorted(v_list_1, reverse=True))
vn2 = np.cumsum([0] + sorted(v_list_2, reverse=True))
vn3 = np.cumsum([0] + sorted(v_list_3, reverse=True))


vmax = 0
n3_max = min(len(v_list_3), W//(w0+3))
for n3 in range(n3_max+1):
    n2_max = min(len(v_list_2), (W - (n3*(w0+3)))//(w0+2))
    for n2 in range(n2_max+1):
        n1_max = min(len(v_list_1), (W - (n3*(w0+3) + n2*(w0+2)))//(w0+1))
        for n1 in range(n1_max+1):
            n0_max = min(len(v_list_0), (W - (n3*(w0+3) + n2*(w0+2) + n1*(w0+1)))//(w0))
            vnow = vn3[n3] + vn2[n2] + vn1[n1] + vn0[n0_max]
            if vnow > vmax:
                vmax = vnow
print(vmax)

Solution (Python):



from random import *
from functools import reduce,partial
from time import time
from pprint import pprint

def readln():
    return list(map(int,input().split(' ')))

def identity(x):
    """Return the input itself."""
    return x

def constant(c):
    """Return an function which always
    returns the input constant c."""
    def const_function(const,*args):
        return const
    return partial(const_function,c)

def inc(c = 1):
    """Return a function which reads an input x and returns x + c as output.
    By default, c equals 1."""
    return lambda x: x + c

def add(*args):
    """Return the sum of the input."""
    def add2(x,y): return x + y
    return reduce(add2,args)

def mapv(f,*lst):
    """Return a vector of the result of map."""
    return list(map(f,*lst))

def vector(*args):
    """Return a vector of input parameters."""
    return args

def sequence(n,f = constant(0)):
    """Return a vector of length n, and initialize the i'th
    item with f(i).By default the vector will initialized with 0."""
    return [f(i) for i in range(0,n)]

def matrix(n,m,f = constant(0)):
    """Return a 2-dim vector which contains n vectors with length m.
    The j's item of vector i will be initialized by f(i,j).By default,
    the vector will be initialized with 0."""
    return [[f(i,j) for j in range(0,m)] for i in range(0,n)]

def flat(v):
    """Return a flat vector which contains the elements of v in their
    origin order.If the input is not a vector, return a vector which
    only contains the input."""
    if not isinstance(v,list): return [v]
    if not v: return []
    return reduce(add,mapv(flat,v))

def partition(v,f = identity):
    """Partition vector v by f(v[i]).
    e.g. partition([1,2,3,1,2,3],identity()) == {1:[1,1,1], 2:[2,2], 3:[3]}
    By default, the vector will be partitioned by identity function."""
    result = {}
    for item in v:
        key = f(item)
        s = result.get(key)
        if s:
            s.append(item)
        else:
            result.update({key:[item]})
    return result

def getValue(key):
    """Return a function which returns the value of key in a hash-map.
    If the key do not exist, it will throw an error."""
    return lambda x: x[key]

def mapValue(f,m):
    """Replace each value in hash-map m with f(value).
    Return the new hash-map."""
    res = {}
    for key in m:
        res.update({key: f(m[key])})
    return res

p = 1000000000 + 7

n,w = readln()
f = [sequence(303) for i in range(0,n+1)]
w1 = -1
f[0] = sequence(303,constant(-1000))
f[0][0] = 0
for i in range(0,n):
    g = [row [:] for row in f]
    wi,vi = readln()
    if w1 < 0 : w1 = wi
    wi -= w1
    for count in range(0,i+1):
        for weight in range(0,303 - wi):
            f[count + 1][weight + wi] = max(
                f[count + 1][weight + wi],
                g[count][weight] + vi)
ans = 0
for count in range(0,n+1):
    for weight in range(0,303):
        if weight + count * w1 <= w:
            ans = max(ans,f[count][weight])
print(ans)

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

p = [[] for i in range(4)]
for i in range(N):
    ww,v = map(int, input().split())
    if i == 0:
        w0 = ww
    p[ww % 4].append(v)
w = [0 for i in range(4)]
v = [0 for i in range(4)]
for i in range(4):
    p[i].sort(reverse=True)
    w[(w0+i)%4] = w0+i
maxv = 0
lens = [len(p[i])+1 for i in range(4)]
for i in range(lens[0]):
    sumw = w[0] * i
    if sumw > W:
        break
    v[0] = sum(p[0][:i])
    maxv = max(maxv, sum(v))
    for j in range(lens[1]):
        sumw = w[0] * i + w[1]*j
        if sumw > W:
            break
        v[1] = sum(p[1][:j])
        maxv = max(maxv, sum(v))
        for k in range(lens[2]):
            sumw = w[0] * i + w[1]*j + w[2]*k
            if sumw > W:
                break
            v[2] = sum(p[2][:k])
            maxv = max(maxv, sum(v))
            for l in range(lens[3]):
                sumw = w[0] * i + w[1]*j + w[2]*k + w[3]*l
                if sumw > W:
                    break
                v[3] = sum(p[3][:l])
                maxv = max(maxv, sum(v))
            v[3] = 0
        v[2] = 0
        v[3] = 0
    v[1] = 0
    v[2] = 0
    v[3] = 0    
v[0] = 0
print(maxv)

Solution (Python):
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())

memo = {i:{} for i in range(N)}

def r(i, g):
    global memo
    if i == N:
        return 0
    elif g in memo[i]:
        return memo[i][g]
    elif g < w[i]:
        a = r(i + 1, g)
    else:
        a = max(r(i + 1, g - w[i]) + v[i], r(i + 1, g))
    
    memo[i][g] = a
    return a

print(r(0, W))

Solution (Python):
import sys

inf = 1 << 32

def solve():
    N, W = map(int, input().split())
    ws = []
    vs = []

    for i in range(N):
        wi, vi = map(int, input().split())
        ws.append(wi)
        vs.append(vi)

    dp = [[[-inf]*(3*N + 1) for j in range(N + 1)]
                              for i in range(N + 1)]

    dp[0][0][0] = 0

    for i in range(N):
        for j in range(N + 1):
            for k in range(3*N + 1):
                dp[i + 1][j][k] = dp[i][j][k]

                if j - 1 >= 0 and k - (ws[i] - ws[0]) >= 0:
                    dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j - 1][k - (ws[i] - ws[0])] + vs[i])

    ans = 0

    for j in range(N + 1):
        for k in range(3*N + 1):
            if ws[0]*j + k <= W:
                ans = max(ans, dp[N][j][k])

    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
n, W = [int(_) for _ in raw_input().split()]

wvs = [[int(_) for _ in raw_input().split()] for i in xrange(n)]

p = {0: 0}

for w, v in wvs:
    for d, dv in p.items():
        p[d + w] = max(p.get(d + w, 0), dv + v)
    m = -1
    for d, dv in sorted(p.items()):
        if dv <= m:
            del p[d]
            continue
        m = max(m, dv)

ans = 0
for d, dv in sorted(p.items()):
    if d > W:
        break
    ans = dv

print(ans)

Solution (Python):



import functools
import sys


MAXSIZE = 2 ** 16
REC_LIMIT = 10000


def main():
    N, W = (int(x) for x in input().split())
    w = [-1 for _ in range(N)]
    v = [-1 for _ in range(N)]
    for i in range(N):
        w[i], v[i] = (int(x) for x in input().split())

    @functools.lru_cache(maxsize=MAXSIZE)
    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)


if __name__ == '__main__':
    sys.setrecursionlimit(REC_LIMIT)
    main()

Solution (Python):
n,W=map(int,raw_input().split())
wv=[map(int,raw_input().split()) for _ in xrange(n)]
diff=[]
for i in xrange(n):
    diff.append(wv[i][0]-wv[0][0])
dp=[[[0]*301 for _ in xrange(n+1)] for _ in xrange(n+1)]
for i in xrange(n):
    w,v=wv[i]
    for j in xrange(i+1):
        for k in xrange(301):
            if k-diff[i]<0:
                dp[i+1][j+1][k]=dp[i][j+1][k]
            else:
                dp[i+1][j+1][k]=max(dp[i][j+1][k],dp[i][j][k-diff[i]]+v)
ans=0
for j in xrange(n+1):
    for k in xrange(301):
        if j*wv[0][0]+k<=W:
            ans=max(ans,dp[n][j][k])
print ans

Solution (Python):
N, W = map(int, input().split())
ws = []
vs = []
for _ in range(N):
    w, v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ans = 0
memo = {0: 0}
for i in range(N):
    w = ws[i]
    v = vs[i]
    tmp = {}
    for w0, v0 in memo.items():
        if w0 + w <= W:
            ans = max(ans, v0 + v)
            if w0 + w in tmp:
                tmp[w0 + w] = max(tmp[w0 + w], v0 + v)
            else:
                tmp[w0 + w] = v0 + v
    for w0, v0 in tmp.items():
        if w0 in memo:
            memo[w0] = max(memo[w0], tmp[w0])
        else:
            memo[w0] = tmp[w0]
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,W = LI()
    a = [LI() for _ in range(n)]
    r = 0
    d = collections.defaultdict(int)
    d[0] = 0
    for w,v in a:
        for e,f in sorted(list(d.items()), key=lambda x: -x[0]):
            if e+w > W:
                continue
            if d[e+w] < d[e] + v:
                d[e+w] = d[e] + v

    return max(d.values())


print(main())