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