Submission #6040643
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
v1 = 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)
masks = list(itertools.product([0, 1], repeat=len(v2)))
w2 = w2 * masks
v2 = 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 |
0 |
Code Size |
2459 Byte |
Status |
RE |
Exec Time |
1437 ms |
Memory |
198288 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
0 / 34 |
0 / 33 |
0 / 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 |
325 ms |
21164 KB |
subtask00_sample_2.txt |
RE |
610 ms |
198288 KB |
subtask00_sample_3.txt |
RE |
150 ms |
12200 KB |
subtask00_sample_4.txt |
RE |
149 ms |
12412 KB |
subtask01_0.txt |
RE |
585 ms |
198244 KB |
subtask01_1.txt |
RE |
620 ms |
198244 KB |
subtask01_10.txt |
RE |
637 ms |
198244 KB |
subtask01_11.txt |
RE |
584 ms |
198288 KB |
subtask01_12.txt |
RE |
583 ms |
198288 KB |
subtask01_13.txt |
RE |
587 ms |
198244 KB |
subtask01_14.txt |
RE |
640 ms |
198244 KB |
subtask01_2.txt |
RE |
584 ms |
198288 KB |
subtask01_3.txt |
RE |
580 ms |
198288 KB |
subtask01_4.txt |
RE |
582 ms |
198244 KB |
subtask01_5.txt |
RE |
580 ms |
198288 KB |
subtask01_6.txt |
RE |
580 ms |
198244 KB |
subtask01_7.txt |
RE |
581 ms |
198244 KB |
subtask01_8.txt |
RE |
586 ms |
198288 KB |
subtask01_9.txt |
RE |
607 ms |
198244 KB |
subtask02_0.txt |
AC |
1428 ms |
21564 KB |
subtask02_1.txt |
AC |
1426 ms |
21564 KB |
subtask02_10.txt |
AC |
1425 ms |
21576 KB |
subtask02_11.txt |
AC |
1437 ms |
21896 KB |
subtask02_12.txt |
AC |
1419 ms |
21732 KB |
subtask02_13.txt |
AC |
153 ms |
12412 KB |
subtask02_14.txt |
AC |
1415 ms |
21504 KB |
subtask02_2.txt |
AC |
1430 ms |
21816 KB |
subtask02_3.txt |
AC |
1433 ms |
21864 KB |
subtask02_4.txt |
AC |
1431 ms |
21824 KB |
subtask02_5.txt |
AC |
1431 ms |
21596 KB |
subtask02_6.txt |
AC |
1431 ms |
21524 KB |
subtask02_7.txt |
AC |
1421 ms |
21484 KB |
subtask02_8.txt |
AC |
1425 ms |
21824 KB |
subtask02_9.txt |
AC |
1427 ms |
21584 KB |
subtask03_0.txt |
AC |
1427 ms |
21828 KB |
subtask03_1.txt |
AC |
1425 ms |
21572 KB |
subtask03_10.txt |
AC |
1426 ms |
21840 KB |
subtask03_11.txt |
AC |
153 ms |
12200 KB |
subtask03_2.txt |
AC |
1411 ms |
23248 KB |
subtask03_3.txt |
AC |
1420 ms |
23304 KB |
subtask03_4.txt |
AC |
1432 ms |
21848 KB |
subtask03_5.txt |
AC |
1403 ms |
21640 KB |
subtask03_6.txt |
AC |
1421 ms |
23364 KB |
subtask03_7.txt |
AC |
1429 ms |
23320 KB |
subtask03_8.txt |
AC |
1428 ms |
21828 KB |
subtask03_9.txt |
AC |
1418 ms |
21520 KB |