Submission #28077508

---

Source Code Expand

from bisect import *
from collections import defaultdict

n, W = map(int, input().split())
vl, wl = [], []
for _ in range(n):
    v, w = map(int, input().split())
    vl.append(v); wl.append(w)

def solve1():
    ### 半分全列挙
    vl1, vl2 = vl[:n//2], vl[n//2:]
    wl1, wl2 = wl[:n//2], wl[n//2:]
    
    d1 = defaultdict(int)
    for f in range(1 << len(vl1)):
        tmp_v = tmp_w = 0
        for i in range(len(vl1)):
            if (f >> i) & 1:
                tmp_v += vl1[i]
                tmp_w += wl1[i]
        d1[tmp_w] = max(d1[tmp_w], tmp_v)
    
    d2 = defaultdict(int)
    for f in range(1 << len(vl2)):
        tmp_v = tmp_w = 0
        for i in range(len(vl2)):
            if (f >> i) & 1:
                tmp_v += vl2[i]
                tmp_w += wl2[i]
        d2[tmp_w] = max(d2[tmp_w], tmp_v)
    
    keys = sorted(d2.keys())
    for i in range(len(keys) - 1):
        k1, k2 = keys[i], keys[i+1]
        if d2[k2] < d2[k1]: d2[k2] = d2[k1]
    
    res = 0
    for w1 in d1:
        if w1 > W: continue
        j = bisect_right(keys, W - w1)
        w2 = keys[j-1]
        res = max(res, d1[w1] + d2[w2])
    return res

def solve2():
    ### wを横軸にしたDP
    max_w = min(W, n * 1000)
    dp = [0] * (max_w + 1)
    
    for i in range(n):
        v, w = vl[i], wl[i]
        for j in range(max_w, w-1, -1):
            dp[j] = max(dp[j], dp[j-w] + v)
    return dp[min(W, max_w)]

def solve3():
    ### vを横軸にしたDP
    max_v = n * 1000
    dp = [0] + [float('inf')] * max_v
    
    for i in range(n):
        v, w = vl[i], wl[i]
        for j in range(max_v, v-1, -1):
            dp[j] = min(dp[j], dp[j-v] + w)
    
    res = 0
    for i in range(max_v + 1):
        if dp[i] <= W: res = i
    return res

if n <= 30:
    print(solve1())
elif max(wl) <= 1000:
    print(solve2())
else:
    print(solve3())

Submission Info

Judge Result