Submission #6040769
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():
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 = list(itertools.product([0, 1], repeat=len(v2)))
w2 = (w2 * masks).sum(axis=1)
v2 = (v2 * masks).sum(axis=1)
remains = M - w2
ok = remains >= 0
idx = np.searchsorted(w1, remains[ok], side='right') - 1
return int((v2[ok] + v1[idx]).max())
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 |
2106 Byte |
Status |
AC |
Exec Time |
1452 ms |
Memory |
31256 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 |
148 ms |
12424 KB |
subtask00_sample_2.txt |
AC |
329 ms |
31216 KB |
subtask00_sample_3.txt |
AC |
149 ms |
12424 KB |
subtask00_sample_4.txt |
AC |
149 ms |
12424 KB |
subtask01_0.txt |
AC |
329 ms |
31128 KB |
subtask01_1.txt |
AC |
382 ms |
31216 KB |
subtask01_10.txt |
AC |
330 ms |
31128 KB |
subtask01_11.txt |
AC |
331 ms |
31128 KB |
subtask01_12.txt |
AC |
331 ms |
31128 KB |
subtask01_13.txt |
AC |
380 ms |
31128 KB |
subtask01_14.txt |
AC |
329 ms |
31216 KB |
subtask01_2.txt |
AC |
328 ms |
31256 KB |
subtask01_3.txt |
AC |
329 ms |
31216 KB |
subtask01_4.txt |
AC |
326 ms |
31216 KB |
subtask01_5.txt |
AC |
332 ms |
31216 KB |
subtask01_6.txt |
AC |
328 ms |
31128 KB |
subtask01_7.txt |
AC |
352 ms |
31128 KB |
subtask01_8.txt |
AC |
327 ms |
31216 KB |
subtask01_9.txt |
AC |
330 ms |
31216 KB |
subtask02_0.txt |
AC |
1433 ms |
21812 KB |
subtask02_1.txt |
AC |
1439 ms |
21824 KB |
subtask02_10.txt |
AC |
1445 ms |
21828 KB |
subtask02_11.txt |
AC |
1442 ms |
21944 KB |
subtask02_12.txt |
AC |
1422 ms |
21720 KB |
subtask02_13.txt |
AC |
151 ms |
12424 KB |
subtask02_14.txt |
AC |
1419 ms |
21748 KB |
subtask02_2.txt |
AC |
1441 ms |
21768 KB |
subtask02_3.txt |
AC |
1443 ms |
21848 KB |
subtask02_4.txt |
AC |
1445 ms |
23348 KB |
subtask02_5.txt |
AC |
1442 ms |
21848 KB |
subtask02_6.txt |
AC |
1445 ms |
23204 KB |
subtask02_7.txt |
AC |
1426 ms |
21724 KB |
subtask02_8.txt |
AC |
1442 ms |
22008 KB |
subtask02_9.txt |
AC |
1442 ms |
21848 KB |
subtask03_0.txt |
AC |
1441 ms |
21816 KB |
subtask03_1.txt |
AC |
1443 ms |
21820 KB |
subtask03_10.txt |
AC |
1442 ms |
21840 KB |
subtask03_11.txt |
AC |
153 ms |
12464 KB |
subtask03_2.txt |
AC |
1431 ms |
23256 KB |
subtask03_3.txt |
AC |
1435 ms |
23292 KB |
subtask03_4.txt |
AC |
1450 ms |
21852 KB |
subtask03_5.txt |
AC |
1428 ms |
21708 KB |
subtask03_6.txt |
AC |
1452 ms |
21832 KB |
subtask03_7.txt |
AC |
1448 ms |
23340 KB |
subtask03_8.txt |
AC |
1432 ms |
21832 KB |
subtask03_9.txt |
AC |
1434 ms |
21776 KB |