src/opt/knapsack/mixed/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | template <class T> | ||
| 8 | class knapsack_mixed { | ||
| 9 | vec<T> f; | ||
| 10 | |||
| 11 | public: | ||
| 12 | 252 | CEXPE knapsack_mixed(u32 max_weight) NE : f(max_weight + 1) {} | |
| 13 | // count = 0 -> inf | ||
| 14 | 6483 | CEXP void add(u32 weight, T value, u32 count = 1) NE { | |
| 15 |
2/2✓ Branch 1 taken 1920 times.
✓ Branch 2 taken 4563 times.
|
6483 | if (cu32 M = (u32)f.size() - 1; !count) |
| 16 |
2/2✓ Branch 4 taken 10768240 times.
✓ Branch 5 taken 1920 times.
|
10770160 | flt_ (u32, i, weight, M + 1) f[i] = max(f[i], f[i - weight] + value); |
| 17 | else | ||
| 18 |
2/2✓ Branch 2 taken 707171 times.
✓ Branch 3 taken 4563 times.
|
711734 | flt_ (u32, w, 0, weight) { |
| 19 | 707171 | vec<T> q1, q2; | |
| 20 | 707171 | u32 l = 0; | |
| 21 |
2/2✓ Branch 0 taken 23347252 times.
✓ Branch 1 taken 707171 times.
|
24054423 | flt_ (u32, i, 0, (M - w) / weight + 1) { |
| 22 | 23347252 | T& x = f[w + weight * i]; | |
| 23 |
6/6✓ Branch 3 taken 22979012 times.
✓ Branch 4 taken 15083662 times.
✓ Branch 6 taken 14715422 times.
✓ Branch 7 taken 8263590 times.
✓ Branch 8 taken 14715422 times.
✓ Branch 9 taken 23347252 times.
|
38062674 | while (l < q1.size() && (T)x - value * (T)i >= q2.back()) q1.pop_back(), q2.pop_back(); |
| 24 | 23347252 | q1.push_back((T)i), q2.push_back((T)x - value * (T)i); | |
| 25 |
5/6✓ Branch 1 taken 30632574 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 7285322 times.
✓ Branch 5 taken 23347252 times.
✓ Branch 6 taken 7285322 times.
✓ Branch 7 taken 23347252 times.
|
30632574 | while (l < q1.size() && q1[l] < T(i - count)) ++l; |
| 26 | 23347252 | x = max(x, q2[l] + value * (T)i); | |
| 27 | } | ||
| 28 | } | ||
| 29 | 6483 | } | |
| 30 | 126 | ND vec<T> CR result() CNE { return f; } | |
| 31 | }; | ||
| 32 | |||
| 33 | } // namespace tifa_libs | ||
| 34 |