Submission #6040338


Source Code Expand

import itertools
import os
import sys
from collections import defaultdict

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 <= M].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 となる最大の価値
    dp = defaultdict(lambda: 0)
    dp[W[0]] = V[0]
    for i in range(1, N):
        items = list(dp.items())
        for w, v in items:
            dp[w + W[i]] = max(dp[w + W[i]], v + V[i])
    ret = 0
    for w, v in dp.items():
        if w <= M:
            ret = max(ret, v)
    return ret


def knapsack_v():
    # 価値に対して重みを最小化
    # dp[v]: 価値が v となる最小の重さ
    dp = defaultdict(lambda: INF)
    dp[V[0]] = W[0]
    for i in range(1, N):
        items = list(dp.items())
        for v, w in items:
            dp[v + V[i]] = min(dp[v + V[i]], w + W[i])
    ret = 0
    for v, w in dp.items():
        if w <= M:
            ret = max(ret, v)
    return ret


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 0
Code Size 2377 Byte
Status WA
Exec Time 2110 ms
Memory 28768 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 0 / 34 0 / 33 0 / 33
Status
AC × 3
WA × 1
AC × 18
WA × 1
AC × 2
WA × 1
TLE × 14
AC × 2
WA × 1
TLE × 11
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 WA 159 ms 12820 KB
subtask00_sample_2.txt AC 507 ms 28768 KB
subtask00_sample_3.txt AC 152 ms 12468 KB
subtask00_sample_4.txt AC 153 ms 12468 KB
subtask01_0.txt AC 494 ms 28768 KB
subtask01_1.txt AC 499 ms 28768 KB
subtask01_10.txt AC 494 ms 28768 KB
subtask01_11.txt AC 488 ms 28768 KB
subtask01_12.txt AC 495 ms 28768 KB
subtask01_13.txt AC 489 ms 28768 KB
subtask01_14.txt AC 523 ms 28768 KB
subtask01_2.txt AC 489 ms 28768 KB
subtask01_3.txt AC 513 ms 28768 KB
subtask01_4.txt AC 490 ms 28768 KB
subtask01_5.txt AC 633 ms 28768 KB
subtask01_6.txt AC 492 ms 28768 KB
subtask01_7.txt AC 491 ms 28768 KB
subtask01_8.txt AC 499 ms 28768 KB
subtask01_9.txt AC 489 ms 28768 KB
subtask02_0.txt TLE 2110 ms 22812 KB
subtask02_1.txt TLE 2109 ms 22428 KB
subtask02_10.txt TLE 2109 ms 22428 KB
subtask02_11.txt TLE 2110 ms 22172 KB
subtask02_12.txt TLE 2110 ms 21916 KB
subtask02_13.txt AC 177 ms 12468 KB
subtask02_14.txt TLE 2110 ms 22428 KB
subtask02_2.txt TLE 2109 ms 22684 KB
subtask02_3.txt TLE 2110 ms 22300 KB
subtask02_4.txt TLE 2110 ms 22300 KB
subtask02_5.txt TLE 2109 ms 21788 KB
subtask02_6.txt TLE 2109 ms 22300 KB
subtask02_7.txt TLE 2109 ms 21916 KB
subtask02_8.txt TLE 2110 ms 22428 KB
subtask02_9.txt TLE 2110 ms 22172 KB
subtask03_0.txt TLE 2110 ms 22172 KB
subtask03_1.txt TLE 2109 ms 23580 KB
subtask03_10.txt TLE 2109 ms 21660 KB
subtask03_11.txt AC 178 ms 12468 KB
subtask03_2.txt TLE 2110 ms 21660 KB
subtask03_3.txt TLE 2109 ms 21148 KB
subtask03_4.txt TLE 2109 ms 20892 KB
subtask03_5.txt TLE 2109 ms 21148 KB
subtask03_6.txt TLE 2109 ms 21276 KB
subtask03_7.txt TLE 2109 ms 20764 KB
subtask03_8.txt TLE 2109 ms 21276 KB
subtask03_9.txt TLE 2109 ms 23452 KB