Submission #6040525


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)
    # 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)
    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

Submission Time
Task D - ナップサック問題
User nohtaray
Language Python (3.4.3)
Score 100
Code Size 2175 Byte
Status AC
Exec Time 1437 ms
Memory 28820 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 34 / 34 33 / 33 33 / 33
Status
AC × 4
AC × 19
AC × 17
AC × 14
Set Name Test Cases
Sample subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask1 subtask01_0.txt, subtask01_1.txt, subtask01_10.txt, subtask01_11.txt, subtask01_12.txt, subtask01_13.txt, subtask01_14.txt, subtask01_2.txt, subtask01_3.txt, subtask01_4.txt, subtask01_5.txt, subtask01_6.txt, subtask01_7.txt, subtask01_8.txt, subtask01_9.txt, subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask2 subtask02_0.txt, subtask02_1.txt, subtask02_10.txt, subtask02_11.txt, subtask02_12.txt, subtask02_13.txt, subtask02_14.txt, subtask02_2.txt, subtask02_3.txt, subtask02_4.txt, subtask02_5.txt, subtask02_6.txt, subtask02_7.txt, subtask02_8.txt, subtask02_9.txt, subtask00_sample_1.txt, subtask00_sample_3.txt
Subtask3 subtask03_0.txt, subtask03_1.txt, subtask03_10.txt, subtask03_11.txt, subtask03_2.txt, subtask03_3.txt, subtask03_4.txt, subtask03_5.txt, subtask03_6.txt, subtask03_7.txt, subtask03_8.txt, subtask03_9.txt, subtask00_sample_1.txt, subtask00_sample_4.txt
Case Name Status Exec Time Memory
subtask00_sample_1.txt AC 295 ms 21148 KB
subtask00_sample_2.txt AC 484 ms 28820 KB
subtask00_sample_3.txt AC 148 ms 12180 KB
subtask00_sample_4.txt AC 148 ms 12520 KB
subtask01_0.txt AC 481 ms 28608 KB
subtask01_1.txt AC 490 ms 28480 KB
subtask01_10.txt AC 489 ms 28820 KB
subtask01_11.txt AC 500 ms 28608 KB
subtask01_12.txt AC 492 ms 28608 KB
subtask01_13.txt AC 502 ms 28820 KB
subtask01_14.txt AC 496 ms 28608 KB
subtask01_2.txt AC 485 ms 28820 KB
subtask01_3.txt AC 487 ms 28820 KB
subtask01_4.txt AC 486 ms 28608 KB
subtask01_5.txt AC 638 ms 28820 KB
subtask01_6.txt AC 489 ms 28820 KB
subtask01_7.txt AC 507 ms 28820 KB
subtask01_8.txt AC 506 ms 28608 KB
subtask01_9.txt AC 485 ms 28820 KB
subtask02_0.txt AC 1424 ms 21820 KB
subtask02_1.txt AC 1423 ms 21580 KB
subtask02_10.txt AC 1421 ms 21836 KB
subtask02_11.txt AC 1424 ms 21872 KB
subtask02_12.txt AC 1408 ms 21732 KB
subtask02_13.txt AC 151 ms 12172 KB
subtask02_14.txt AC 1407 ms 21748 KB
subtask02_2.txt AC 1425 ms 21556 KB
subtask02_3.txt AC 1423 ms 21604 KB
subtask02_4.txt AC 1423 ms 23308 KB
subtask02_5.txt AC 1422 ms 21844 KB
subtask02_6.txt AC 1416 ms 21772 KB
subtask02_7.txt AC 1427 ms 22004 KB
subtask02_8.txt AC 1432 ms 21572 KB
subtask02_9.txt AC 1425 ms 21600 KB
subtask03_0.txt AC 1426 ms 21824 KB
subtask03_1.txt AC 1425 ms 21832 KB
subtask03_10.txt AC 1437 ms 21584 KB
subtask03_11.txt AC 156 ms 12520 KB
subtask03_2.txt AC 1408 ms 23000 KB
subtask03_3.txt AC 1416 ms 23280 KB
subtask03_4.txt AC 1430 ms 21588 KB
subtask03_5.txt AC 1406 ms 21712 KB
subtask03_6.txt AC 1419 ms 21908 KB
subtask03_7.txt AC 1421 ms 21568 KB
subtask03_8.txt AC 1419 ms 21584 KB
subtask03_9.txt AC 1413 ms 21524 KB