1# from titan_pylib.others.knapsack_solver import KnapsackSolver
2from bisect import bisect_right
3
4
5class KnapsackSolver:
6
7 def __init__(self, N: int, W: int, VW: list[tuple[int, int]]):
8 self.N: int = N
9 self.W: int = W
10 self.VW: list[tuple[int, int]] = VW
11
12 def solve_hanbunzenrekkyo(self) -> int:
13 def naive(vw):
14 ret = []
15 n = len(vw)
16 for i in range(1 << n):
17 value, weight = 0, 0
18 for j in range(n):
19 if i >> j & 1:
20 value += vw[j][0]
21 weight += vw[j][1]
22 ret.append([weight, value])
23 return ret
24
25 left, right = self.VW[: self.N // 2], self.VW[self.N // 2 :]
26 left_ret = naive(left)
27 left_ret.sort()
28 right_ret = naive(right)
29 right_ret.sort()
30 for i in range(len(right_ret) - 1):
31 right_ret[i + 1][1] = max(right_ret[i + 1][1], right_ret[i][1])
32 ans = -1
33 W = self.W
34 for weight, value in left_ret:
35 if weight > W:
36 break
37 i = bisect_right(right_ret, [W - weight, float("inf")]) - 1
38 ans = max(ans, value + right_ret[i][1])
39 return ans
40
41 def solve_dp_small_weight(self):
42 dp = [-1] * (self.W + 1)
43 W = self.W
44 dp[0] = 0
45 for i, (v, w) in enumerate(self.VW):
46 ep = [-1] * (W + 1)
47 for j in range(W + 1):
48 if dp[j] == -1:
49 continue
50 ep[j] = max(ep[j], dp[j])
51 if j + w <= W:
52 ep[j + w] = max(ep[j + w], dp[j] + v)
53 dp = ep
54 return max(dp)
55
56 def solve_dp_small_value(self) -> int:
57 sum_v = sum(v for v, _ in self.VW)
58 inf = float("inf")
59 dp = [inf] * (sum_v + 1)
60 dp[0] = 0
61 for v, w in self.VW:
62 ep = [inf] * (sum_v + 1)
63 for j in range(sum_v + 1):
64 if dp[j] == inf:
65 continue
66 ep[j] = min(ep[j], dp[j])
67 if j + v <= sum_v:
68 ep[j + v] = min(ep[j + v], dp[j] + w)
69 dp = ep
70 for j in range(sum_v, -1, -1):
71 if dp[j] <= self.W:
72 return j
73 return -1