Submission #6040809

---

Source Code Expand

import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
V, W = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

V = np.array(V)
W = np.array(W)


def knapsack_n():
    assert N <= 30

    # 2個に分けて組み合わせを全探索
    half = N // 2
    v1 = V[:half]
    w1 = W[:half]
    v2 = V[half:]
    w2 = W[half:]

    # 重さ全列挙
    # masks = np.array(np.meshgrid(*([[0, 1]] * len(v1)))).T.reshape(-1, len(v1)).T
    # w1 = np.dot(w1, masks)
    # v1 = np.dot(v1, masks)
    # ↑meshgrid で生成するのめっちゃおそいぞ
    masks = np.array(list(itertools.product([0, 1], repeat=len(v1)))).T
    w1 = np.dot(w1, masks)
    v1 = np.dot(v1, masks)

    # sort
    idx = w1.argsort()
    w1 = w1[idx]
    # cummax
    v1 = np.maximum.accumulate(v1[idx])

    masks = np.array(list(itertools.product([0, 1], repeat=len(v2)))).T
    w2 = np.dot(w2, masks)
    v2 = np.dot(v2, masks)

    remains = M - w2
    ok = remains >= 0
    idx = np.searchsorted(w1, remains[ok], side='right') - 1
    return int((v2[ok] + v1[idx]).max())


def knapsack_w():
    # 重みに対して価値を最大化
    # dp[w]: 価値が w となる最大の価値
    size = W.max() * N + 1
    dp = np.zeros(size, dtype=int)
    for w, v in zip(W, V):
        dp[w:] = np.maximum(dp[w:], dp[:size - w] + v)
    return dp[M]


def knapsack_v():
    # 価値に対して重みを最小化
    # dp[v]: 価値が v となる最小の重さ
    size = V.max() * N + 1
    dp = np.full(size, INF)
    dp[0] = 0
    for w, v in zip(W, V):
        dp[v:] = np.minimum(dp[v:], dp[:size - v] + w)
    return np.where(dp <= M)[0].max()


if N <= 30:
    print(knapsack_n())
elif W.max() <= 1000:
    print(knapsack_w())
elif V.max() <= 1000:
    print(knapsack_v())

Submission Info

Judge Result