Submission #6040660

---

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():
    if N <= 3:
        masks = list(itertools.product([0, 1], repeat=N))
        ws = W * masks
        vs = V * masks
        return vs[ws.sum(axis=1) <= M].sum(axis=1).max()

    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 = list(itertools.product([0, 1], repeat=len(v1)))
    w1 = (w1 * masks).sum(axis=1)
    v1 = (v1 * masks).sum(axis=1)

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

    # masks = np.array(np.meshgrid(*([[0, 1]] * len(v2)))).T.reshape(-1, len(v2)).T
    # w2 = np.dot(w2, masks)
    # v2 = np.dot(v2, masks)
    masks = list(itertools.product([0, 1], repeat=len(v2)))
    w2 = (w2 * masks).sum(axis=1)
    v2 = (v2 * masks).sum(axis=1)

    ans = 0
    for w, v in zip(w2, v2):
        remains = M - w
        if remains < 0:
            continue
        idx = np.searchsorted(w1, remains, side='right') - 1
        ans = max(ans, v + v1[idx])
    return ans


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