Problem:


Huge Knapsack Problem

You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

The total value of the items is as large as possible.

The items have combined weight at most W, that is capacity of the knapsack.

Find the maximum total value of items in the knapsack.

Input

N W
v1 w1
v2 w2
:
vN wN

The first line consists of the integers N and W. In the following N lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Constraints

 1 ≤ N ≤ 40
	

 1 ≤ vi ≤ 1015
	

 1 ≤ wi ≤ 1015

 1 ≤ W ≤ 1015
	

Sample Input 1

4 5
4 2
5 2
2 1
8 3

Sample Output 1

13

Sample Input 2

2 20
5 9
4 10

Sample Output 2

9



Sample input:
4 5
4 2
5 2
2 1
8 3


Sample output:
13

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#1:combinatorial
#1_A
"""
n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [float("inf") for i in range(n+1)]
dp[0] = 0
for i in range(n):
    for j in c:
        if i+j <= n:
            dp[i+j] = min(dp[i+j], dp[i]+1)
print(dp[n])
"""
#1_B
"""
n,w = map(int,input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [0 for i in range(w+1)]
memo = [[] for i in range(w+1)]
for i in range(w):
    for j in range(n):
        if i+b[j][1] <= w and j not in memo[i]:
            if dp[i+b[j][1]] > dp[i]+b[j][0]:
                continue
            else:
                memo[i+b[j][1]] = memo[i]+[j]
                dp[i+b[j][1]] = dp[i]+b[j][0]

print(max(dp))
"""
#1_C
"""
n,w = map(int,input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [0 for i in range(w+1)]
for i in range(w):
    for j in b:
        if i+j[1] <= w:
            dp[i+j[1]] = max(dp[i+j[1]], dp[i]+j[0])
print(dp[w])
"""
#1_D
"""
import bisect

n = int(input())
s = [int(input()) for i in range(n)]
dp = [float("INF") for i in range(n)]
for i in range(n):
    dp[bisect.bisect_left(dp,s[i])] = s[i]
print(bisect.bisect_left(dp,100000000000000))
"""

#1_E
"""
s1 = input()
s2 = input()
n = len(s1)
m = len(s2)
dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = i
for j in range(m+1):
    dp[0][j] = j
for i in range(1,n+1):
    for j in range(1,m+1):
        cost = 0 if s1[i-1] == s2[j-1] else 1
        dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+cost)
print(dp[n][m])
"""
#1_F
"""
import bisect

n,W = map(int,input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [float("INF") for i in range(10001)]
dp[0] = 0
for v,w in b:
    for i in range(10001):
        if 10000-i+v < 10001:
            dp[10000-i+v] = min(dp[10000-i+v], dp[10000-i]+w)
for i in range(1,10000):
    dp[10000-i] = min(dp[10000-i], dp[10001-i])
print(bisect.bisect_right(dp,W)-1)
"""

#1_G
"""
n,W = LI()
g = LIR(n)
"""

#1_H
n,W = LI()
v = [None for i in range(n)]
w = [None for i in range(n)]
for i in range(n):
    v[i],w[i] = LI()
a = [[0,0]]
b = [[0,0]]
m = n//2
for i in range(m):
    for j in range(1<<i):
        a.append([a[j][0]+v[i],a[j][1]+w[i]])
for i in range(n-m):
    for j in range(1<<i):
        b.append([b[j][0]+v[i+m],b[j][1]+w[i+m]])
a.sort(key = lambda x:x[1])
b.sort(key = lambda x:x[1])
ma = b[0][0]
for i in range(1,len(b)):
    if ma > b[i][0]:
        b[i][0] = ma
    else:
        ma = b[i][0]
ans = 0
i = len(b)-1
for v,w in a:
    rem = W-w
    while b[i][1] > rem:
        if i == 0:break
        i -= 1
    if b[i][1] <= rem:
        ans = max(ans,v+b[i][0])
print(ans)
#2:permutaion/path
#2_A
"""
n,e = LI()
v = [[] for i in range(n)]
f = [-1 for i in range(n)]
for i in range(e):
    s,t,d = LI()
    v[s].append([t,d])
    if t == 0:
        f[s] = d
po = [1 for i in range(n+1)]
for i in range(n):
    po[i+1] = po[i]*2
dp = [[float("inf") for i in range(po[n])] for j in range(n)]
dp[0][1] = 0
for j in range(po[n]):
    for x in range(n):
        if po[x]&j:
            for y,d in v[x]:
                if not po[y]&j:
                    dp[y][j|po[y]] = min(dp[y][j|po[y]],dp[x][j]+d)
ans = float("inf")
for i in range(n):
    if f[i] != -1:
        ans = min(ans,dp[i][-1]+f[i])
if ans == float("inf"):
    print(-1)
else:
    print(ans)
"""
#3:pattern

#3_A
"""
h,w = map(int, input().split())
c = [list(map(int, input().split())) for i in range(h)]
dp = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    dp[i][0] = 1 if c[i][0] == 0 else 0
for i in range(w):
    dp[0][i] = 1 if c[0][i] == 0 else 0
for i in range(1,h):
    for j in range(1,w):
        if c[i][j] == 0:
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
ans = 0
for i in dp:
    for j in i:
        ans = max(ans, j)
print(ans**2)
"""

#3_B

#4:counting
#4_A
"""
n,v = LI()
a = LI()
b = LI()
c = LI()
d = LI()
p = defaultdict(int)
q = defaultdict(int)
for i in a:
    for j in b:
        if i+j <= v-2:
            p[i+j] += 1
for i in c:
    for j in d:
        if i+j <= v-2:
            q[i+j] += 1
ans = 0
for i,j in p.items():
    ans += j*q[v-i]
print(ans)
"""


#5:Twelvedfold_Way

#5_A
"""
n,k = map(int, input().split())
ans = k
for i in range(n-1):
    ans *= k
    ans %= 1000000007
print(ans)
"""

#5_B
"""
import sys
sys.setrecursionlimit(10000)
memo = [1,1]
def fact(a):
    if len(memo) > a:
        return memo[a]
    b = a*fact(a-1)
    memo.append(b)
    return b
n,k = map(int, input().split())
if n > k:
    ans = 0
else:
    ans = fact(k)//fact(k-n)
print(ans%1000000007)
"""

#5_C
"""
def comb(a,b):
    return fac[a]*inv[b]*inv[a-b]%mod
n,k = LI()
if n < k:
    print(0)
    quit()
fac = [1 for i in range(k+1)]
for i in range(k):
    fac[i+1] = fac[i]*(i+1)%mod
inv = [None for i in range(k+1)]
inv[k] = pow(fac[k],mod-2,mod)
for i in range(k)[::-1]:
    inv[i] = inv[i+1]*(i+1)%mod
ans = 0
for i in range(k+1):
    if i%2:
        ans -= comb(k,i)*pow(k-i,n,mod)%mod
    else:
        ans += comb(k,i)*pow(k-i,n,mod)%mod
    ans %= mod
print(ans)
"""

#5_D
"""
n,k = map(int, input().split())
import sys
sys.setrecursionlimit(10000)
memo = [1,1]
def fact(a):
    if len(memo) > a:
        return memo[a]
    b = a*fact(a-1)
    memo.append(b)
    return b
ans = fact(n+k-1)//(fact(n)*fact(k-1))%1000000007
print(ans)
"""

#5_E
"""
def comb(a,b):
    return fac[a]*inv[b]*inv[a-b]%mod
n,k = LI()
if n > k:
    print(0)
    quit()
fac = [1 for i in range(k+1)]
for i in range(k):
    fac[i+1] = fac[i]*(i+1)%mod
inv = [None for i in range(k+1)]
inv[k] = pow(fac[k],mod-2,mod)
for i in range(k)[::-1]:
    inv[i] = inv[i+1]*(i+1)%mod
print(comb(k,n))
"""

#5_F
"""
def comb(a,b):
    return fac[a]*inv[b]*inv[a-b]%mod
n,k = LI()
if n < k:
    print(0)
    quit()
fac = [1 for i in range(n+1)]
for i in range(n):
    fac[i+1] = fac[i]*(i+1)%mod
inv = [None for i in range(n+1)]
inv[n] = pow(fac[n],mod-2,mod)
for i in range(n)[::-1]:
    inv[i] = inv[i+1]*(i+1)%mod
print(comb(n-1,n-k))
"""
#5_G

#5_H

#5_I

#5_J

#5_K

#5_L

Submission status: Accepted

Solution code:
import bisect
 
n,maxw = map(int , input().split())
data1 = [[0,0]] #data1enu[i]:iのbitが立ってる品物の価値、重さの総和
data2 = [[0,0]]
nn = n // 2

for i in range(nn):
    v,w = map(int , input().split())
    sz = len(data1)
    for j in range(sz):
        ppp = data1[j][:]
        ppp[0] += w
        ppp[1] += v
        data1.append(ppp)

for i in range(n-nn):
    v,w = map(int , input().split())
    sz = len(data2)
    for j in range(sz):
        ppp = data2[j][:]
        ppp[0] += w
        ppp[1] += v
        data2.append(ppp)

data2.sort()
maxx = 0
ss = len(data2)
for i in range(ss):
    maxx = max(maxx , data2[i][1])
    data2[i][1] = maxx
ans = 0
ss = len(data1)
for i in range(ss):
    ww , vv = data1[i]
    if (ww > maxw) : continue
    amari = maxw - ww
    ans = max (ans , vv + data2[bisect.bisect_right(data2, [amari , float('inf')])-1][1])

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DPL_1_H: Huge Knapsack Problem
# 0/1 Knapsack using Branch and Bound
# https://www.youtube.com/watch?v=yV1d-b_NeK8

from heapq import heappush, heappop


def max_value(t, xs):
    def _cost(weight, value, i):
        for j in range(i, n):
            v, w = xs[j]
            if weight + w > t:
                return (-value, -value - (v/w)*(t-weight))
            weight += w
            value += v
        return (-value, -value*1.0)

    n = len(xs)
    xs.sort(key=lambda x: x[0]/x[1], reverse=True)
    u, c = _cost(0, 0, 0)
    heap = [(c, u, 0, 0, 0)]
    maxcost = u
    while heap:
        cost, upper, weight, value, i = heappop(heap)
        if cost > maxcost:
            break
        if i < n:
            v, w = xs[i]
            if weight+w <= t:
                heappush(heap, (cost, upper, weight+w, value+v, i+1))
            u, c = _cost(weight, value, i+1)
            if c < maxcost:
                if u < maxcost:
                    maxcost = u
                heappush(heap, (c, u, weight, value, i+1))

    return -maxcost


def run():
    n, t = [int(i) for i in input().split()]
    xs = []

    for _ in range(n):
        v, w = [int(i) for i in input().split()]
        xs.append((v, w))

    print(max_value(t, xs))


if __name__ == '__main__':
    run()

Submission status: Accepted

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

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

def make(S):
    T = {0: 0}
    for v, w in S:
        T0 = dict(T)
        for k, val in T.items():
            if k+w > W:
                continue
            if k+w in T0:
                T0[k+w] = max(T0[k+w], val + v)
            else:
                T0[k+w] = val + v
        T = T0
    v = 0
    R = []
    for k in sorted(T):
        v = max(v, T[k])
        R.append((k, v))
    return R

def solve(T0, T1):
    T0.sort()
    T1.sort(reverse=1)

    it = iter(T1); k1, v1 = next(it)
    yield 0
    for k0, v0 in T0:
        while k0 + k1 > W:
            k1, v1 = next(it)
        yield v0 + v1


T0 = make(S[:N//2])
T1 = make(S[N//2:])

print(max(solve(T0, T1)))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right


def meet_in_the_middle(a: list, limit: int) -> tuple:
    first_v, first_w, second_v, second_w = [], [], [], []
    for items, v_append, w_append in (
            (a[:len(a)//2], first_v.append, first_w.append),
            (a[len(a)//2:], second_v.append, second_w.append)
    ):
        enumerated = [(0, 0)]
        for v, w in items:
            enumerated += [(w+_w, v+_v) for _w, _v in enumerated]

        enumerated.sort()
        enumerated = enumerated[:bisect_right(enumerated, (limit, float("inf")))] + [(limit+1, 0)]
        max_v = -1
        for (cw, cv), (nw, nv) in zip(enumerated, enumerated[1:]):
            if cw < nw and max_v < cv:
                v_append(cv)
                w_append(cw)
                max_v = cv

    return (first_v, first_w), (second_v, second_w)


N, W = map(int, input().split())
a = [list(map(int, l.split())) for l in sys.stdin]

(first_v, first_w), (second_v, second_w) = meet_in_the_middle(a, W)
ans = 0
for v, w in zip(first_v, first_w):
    i = bisect_right(second_w, W-w)-1
    new_v = v + second_v[i]
    if ans < new_v:
        ans = new_v
print(ans)

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
v = [0]*N;w = [0]*N
 
for i in range(N):
    v[i],w[i] = map(int,input().split())
 
value = [0 for i in range(W+1)]
for i in range(N):
    for j in range(W,W/2,-1):
        if j<w[i]:
            value[j] = value[j]
        else:
            value[j] = max(value[j],value[j-w[i]]+v[i])
 
print(value[W])