Source code for titan_pylib.others.knapsack_solver

 1from bisect import bisect_right
 2
 3

[docs]
 4class KnapsackSolver:
 5
 6    def __init__(self, N: int, W: int, VW: list[tuple[int, int]]):
 7        self.N: int = N
 8        self.W: int = W
 9        self.VW: list[tuple[int, int]] = VW
10

[docs]
11    def solve_hanbunzenrekkyo(self) -> int:
12        def naive(vw):
13            ret = []
14            n = len(vw)
15            for i in range(1 << n):
16                value, weight = 0, 0
17                for j in range(n):
18                    if i >> j & 1:
19                        value += vw[j][0]
20                        weight += vw[j][1]
21                ret.append([weight, value])
22            return ret
23
24        left, right = self.VW[: self.N // 2], self.VW[self.N // 2 :]
25        left_ret = naive(left)
26        left_ret.sort()
27        right_ret = naive(right)
28        right_ret.sort()
29        for i in range(len(right_ret) - 1):
30            right_ret[i + 1][1] = max(right_ret[i + 1][1], right_ret[i][1])
31        ans = -1
32        W = self.W
33        for weight, value in left_ret:
34            if weight > W:
35                break
36            i = bisect_right(right_ret, [W - weight, float("inf")]) - 1
37            ans = max(ans, value + right_ret[i][1])
38        return ans

39

[docs]
40    def solve_dp_small_weight(self):
41        dp = [-1] * (self.W + 1)
42        W = self.W
43        dp[0] = 0
44        for i, (v, w) in enumerate(self.VW):
45            ep = [-1] * (W + 1)
46            for j in range(W + 1):
47                if dp[j] == -1:
48                    continue
49                ep[j] = max(ep[j], dp[j])
50                if j + w <= W:
51                    ep[j + w] = max(ep[j + w], dp[j] + v)
52            dp = ep
53        return max(dp)

54

[docs]
55    def solve_dp_small_value(self) -> int:
56        sum_v = sum(v for v, _ in self.VW)
57        inf = float("inf")
58        dp = [inf] * (sum_v + 1)
59        dp[0] = 0
60        for v, w in self.VW:
61            ep = [inf] * (sum_v + 1)
62            for j in range(sum_v + 1):
63                if dp[j] == inf:
64                    continue
65                ep[j] = min(ep[j], dp[j])
66                if j + v <= sum_v:
67                    ep[j + v] = min(ep[j + v], dp[j] + w)
68            dp = ep
69        for j in range(sum_v, -1, -1):
70            if dp[j] <= self.W:
71                return j
72        return -1