ok so first of all I am doing this mostly to deepen my understanding and I might not have understood something so correct me if I am wrong↵
↵
We all know the famous knapsack problem but just to be sure↵
↵
### Problem Statement↵
given $N$ items each with a cost and value/gain, you have a bag with capacity $W$, what's the maximum value you can fit in that bag↵
↵
it's a standard dynamic programming problem↵
I would assume you know how do it with 1 dimensional dp↵
↵
### subset sums↵
### optimizing with bitsets↵
first optimization, say you have $N$ items with values and you want to check whether there exists a subset which sum up to $S$↵
↵
↵
~~~~~↵
ll sum = 0;↵
for (ll x : vals) sum += x;↵
vector<ll> dp(sum+1, 0);↵
dp[0] = 1;↵
for (ll i = 0; i < n; i++) {↵
for (ll j = sum; j >= vals[i]; j--) {↵
if (dp[j-vals[i]]) dp[j] = 1;↵
}↵
}↵
~~~~~↵
this would be the first code that comes to mind which runs in $O(N \cdot sums)$ and most of the time this would be enough, but it can be optimized a little bit using bitsets↵
↵
~~~~~↵
const ll MX = (ll) 1e6 + 5;↵
bitset<MX> dp;↵
dp[0] = 1;↵
for (ll i = 0; i < n; i++) {↵
dp |= (dp << vals[i]);↵
}↵
~~~~~↵
now this code does the exact same thing but now it runs in $O(\frac{N \cdot sums}{64})$ which might not be a lot but it would definitely come in handy + the code it a lot shorter and cleaner :) ↵
↵
ok so explanation, here we only want to check whether something is reachable or not, aka true or false, aka 0 or 1 so basically in this line `if (dp[j-vals[i]]) dp[j] = 1;` could replace it with `dp[j] |= dp[j-vals[i]]`↵
so for every number i, we or it with the one `vals[i]` away from it if we treat each value as a bit (which is literally what bitsets do) this would be just `dp |= (dp << vals[i]);` which is what we have done :)↵
↵
the time complexity is divided by 64 because bitsets run $64$ operations all at once, so if you wanna do some change to 64 values it would be cut down from $64$ to $1$ operation↵
↵
really hope this makes sense xD↵
↵
### bounded knapsack or 0/k knapsack↵
### binary splitting↵
I really love this optimization, I don't know if the names I gave this section is correct or not but yea who cares lets get into it↵
↵
say you have $N$ items each having a cost, a value and a frequency/count, you want to know the maximum value you can get with weight less than or equal W↵
↵
the first solution that comes to mind is do just repeat the knapsack for each element $freq$ times↵
↵
↵
~~~~~↵
vector<ll> dp(W+1, 0);↵
↵
for (ll i = 0; i < n; i++) {↵
ll cnt = freq[i];↵
for (ll rep = 0; rep < cnt; rep++) {↵
for (ll j = W; j >= w[i]; j--) {↵
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);↵
}↵
}↵
}↵
~~~~~↵
this is quite suboptimal tho, it runs in $O(W \cdot \sum_{i=0}^{n-1} freq_i)$↵
↵
now comes the optimization :)↵
say I would take $k$ of the $i$-th item, then $k$ can be represented as some number in base-2 or binary, so we keep decomposing the $i$-th item's frequency into powers of $2$ then we can consider each power of 2 frequency as a separate item with it's own value and cost, and suddenly we are just doing good old 0/1 knapsack↵
↵
I will give an example here, say the frequency of some item is $13$, it's value is $3$ and the cost of each one of it is $4$↵
here I would represent each item as $(frequency, cost, value)$↵
↵
we decompose the frequency into smaller items then we get this ${(1, 4, 3), (2, 4 \cdot 2, 3 \cdot 2), (4, 4 \cdot 4, 3 \cdot 4)}$ now there is a problem the remaining frequency is $6$ which is not a power of $2$ and we have already taken the numbers $2$ and $4$, we _can_ split this $6$ into another elements of frequencies $2$ and $4$, however that's not needed we can just leave it a $6$ so the final list is ↵
↵
${(1, 4, 3), (2, 4 \cdot 2, 3 \cdot 2), (4, 4 \cdot 4, 3 \cdot 4), (6, 4 \cdot 6, 3 \cdot 6)}$ or just↵
${(1, 4, 3), (2, 8, 6), (4, 16, 12), (6, 24, 18)}$↵
↵
now we do this for each item and we are doing knapsack onto the values and costs without having to care about the frequencies, we just have more items↵
↵
now for the code↵
↵
~~~~~↵
vector<ll> vals, costs;↵
for (ll i = 0; i < n; i++) {↵
ll cnt = freq[i];↵
for (ll b = 1; cnt > 0; b *= 2) {↵
ll take = min(b, cnt);↵
ll c = w[i] * take;↵
ll val = v[i] * take;↵
vals.push_back(val);↵
costs.push_back(c);↵
cnt -= take;↵
}↵
}↵
↵
vector<ll> dp(W+1, 0);↵
↵
ll m = (ll) vals.size();↵
for (ll i = 0; i < m; i++) {↵
for (ll j = W; j >= costs[i]; j--) {↵
dp[j] = max(dp[j], dp[j-costs[i]] + vals[i]);↵
}↵
}↵
~~~~~↵
↵
here $m$ is the time and space factor, so each item is split into $log_2(freq_i)$ items, we do this $n$ times so $m = \sum_{i=0}^{n-1} log_2(freq_i)$↵
↵
now the time complexity is $O(W \cdot m)$ or $O(W \cdot \sum_{i=0}^{n-1} log_2(freq_i)$↵
which is much better than the previous $O(W \cdot \sum_{i=0}^{n-1} freq_i)$↵
↵
now the problem is that making all those items may be costly memory wise so we can do the splitting in a loop without actually storing the items↵
↵
which would look like this↵
↵
~~~~~↵
vector<ll> dp(W+1, 0);↵
↵
for (ll i = 0; i < n; i++) {↵
ll cnt = freq[i];↵
↵
for (ll b = 1; cnt > 0; b *= 2) {↵
ll take = min(b, cnt);↵
ll c = w[i] * take;↵
ll val = v[i] * take;↵
↵
for (ll j = W; j >= c; j--) {↵
dp[j] = max(dp[j], dp[j-c] + val);↵
}↵
cnt -= take;↵
}↵
}↵
~~~~~↵
really nothing fancy we are just doing the splitting and the knapsack together instead of storing every one of the $log_2(freq_i)$ items $n$ times and now the space complexity is $O(W + m)$ ↵
↵
↵
and that's about it for the blog :)↵
thank you very much for reading up till here and please give me your feedback :)↵
if you want me to try and explain another technique, data structure or something tell me or if you want some clarification↵
thx and have a good day <3↵
↵
some problems with that need the optimizations I talked about↵
↵
Binary Splitting↵
- [problem:755F]↵
↵
Bitset↵
- [problem:577B]↵
- [problem:1856E1]↵
↵
↵
↵
↵
↵
↵
We all know the famous knapsack problem but just to be sure↵
↵
### Problem Statement↵
given $N$ items each with a cost and value/gain, you have a bag with capacity $W$, what's the maximum value you can fit in that bag↵
↵
it's a standard dynamic programming problem↵
I would assume you know how do it with 1 dimensional dp↵
↵
### subset sums↵
### optimizing with bitsets↵
first optimization, say you have $N$ items with values and you want to check whether there exists a subset which sum up to $S$↵
↵
↵
~~~~~↵
ll sum = 0;↵
for (ll x : vals) sum += x;↵
vector<ll> dp(sum+1, 0);↵
dp[0] = 1;↵
for (ll i = 0; i < n; i++) {↵
for (ll j = sum; j >= vals[i]; j--) {↵
if (dp[j-vals[i]]) dp[j] = 1;↵
}↵
}↵
~~~~~↵
this would be the first code that comes to mind which runs in $O(N \cdot sums)$ and most of the time this would be enough, but it can be optimized a little bit using bitsets↵
↵
~~~~~↵
const ll MX = (ll) 1e6 + 5;↵
bitset<MX> dp;↵
dp[0] = 1;↵
for (ll i = 0; i < n; i++) {↵
dp |= (dp << vals[i]);↵
}↵
~~~~~↵
now this code does the exact same thing but now it runs in $O(\frac{N \cdot sums}{64})$ which might not be a lot but it would definitely come in handy + the code it a lot shorter and cleaner :) ↵
↵
ok so explanation, here we only want to check whether something is reachable or not, aka true or false, aka 0 or 1 so basically in this line `if (dp[j-vals[i]]) dp[j] = 1;` could replace it with `dp[j] |= dp[j-vals[i]]`↵
so for every number i, we or it with the one `vals[i]` away from it if we treat each value as a bit (which is literally what bitsets do) this would be just `dp |= (dp << vals[i]);` which is what we have done :)↵
↵
the time complexity is divided by 64 because bitsets run $64$ operations all at once, so if you wanna do some change to 64 values it would be cut down from $64$ to $1$ operation↵
↵
really hope this makes sense xD↵
↵
### bounded knapsack or 0/k knapsack↵
### binary splitting↵
I really love this optimization, I don't know if the names I gave this section is correct or not but yea who cares lets get into it↵
↵
say you have $N$ items each having a cost, a value and a frequency/count, you want to know the maximum value you can get with weight less than or equal W↵
↵
the first solution that comes to mind is do just repeat the knapsack for each element $freq$ times↵
↵
↵
~~~~~↵
vector<ll> dp(W+1, 0);↵
↵
for (ll i = 0; i < n; i++) {↵
ll cnt = freq[i];↵
for (ll rep = 0; rep < cnt; rep++) {↵
for (ll j = W; j >= w[i]; j--) {↵
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);↵
}↵
}↵
}↵
~~~~~↵
this is quite suboptimal tho, it runs in $O(W \cdot \sum_{i=0}^{n-1} freq_i)$↵
↵
now comes the optimization :)↵
say I would take $k$ of the $i$-th item, then $k$ can be represented as some number in base-2 or binary, so we keep decomposing the $i$-th item's frequency into powers of $2$ then we can consider each power of 2 frequency as a separate item with it's own value and cost, and suddenly we are just doing good old 0/1 knapsack↵
↵
I will give an example here, say the frequency of some item is $13$, it's value is $3$ and the cost of each one of it is $4$↵
here I would represent each item as $(frequency, cost, value)$↵
↵
we decompose the frequency into smaller items then we get this ${(1, 4, 3), (2, 4 \cdot 2, 3 \cdot 2), (4, 4 \cdot 4, 3 \cdot 4)}$ now there is a problem the remaining frequency is $6$ which is not a power of $2$ and we have already taken the numbers $2$ and $4$, we _can_ split this $6$ into another elements of frequencies $2$ and $4$, however that's not needed we can just leave it a $6$ so the final list is ↵
↵
${(1, 4, 3), (2, 4 \cdot 2, 3 \cdot 2), (4, 4 \cdot 4, 3 \cdot 4), (6, 4 \cdot 6, 3 \cdot 6)}$ or just↵
${(1, 4, 3), (2, 8, 6), (4, 16, 12), (6, 24, 18)}$↵
↵
now we do this for each item and we are doing knapsack onto the values and costs without having to care about the frequencies, we just have more items↵
↵
now for the code↵
↵
~~~~~↵
vector<ll> vals, costs;↵
for (ll i = 0; i < n; i++) {↵
ll cnt = freq[i];↵
for (ll b = 1; cnt > 0; b *= 2) {↵
ll take = min(b, cnt);↵
ll c = w[i] * take;↵
ll val = v[i] * take;↵
vals.push_back(val);↵
costs.push_back(c);↵
cnt -= take;↵
}↵
}↵
↵
vector<ll> dp(W+1, 0);↵
↵
ll m = (ll) vals.size();↵
for (ll i = 0; i < m; i++) {↵
for (ll j = W; j >= costs[i]; j--) {↵
dp[j] = max(dp[j], dp[j-costs[i]] + vals[i]);↵
}↵
}↵
~~~~~↵
↵
here $m$ is the time and space factor, so each item is split into $log_2(freq_i)$ items, we do this $n$ times so $m = \sum_{i=0}^{n-1} log_2(freq_i)$↵
↵
now the time complexity is $O(W \cdot m)$ or $O(W \cdot \sum_{i=0}^{n-1} log_2(freq_i)$↵
which is much better than the previous $O(W \cdot \sum_{i=0}^{n-1} freq_i)$↵
↵
now the problem is that making all those items may be costly memory wise so we can do the splitting in a loop without actually storing the items↵
↵
which would look like this↵
↵
~~~~~↵
vector<ll> dp(W+1, 0);↵
↵
for (ll i = 0; i < n; i++) {↵
ll cnt = freq[i];↵
↵
for (ll b = 1; cnt > 0; b *= 2) {↵
ll take = min(b, cnt);↵
ll c = w[i] * take;↵
ll val = v[i] * take;↵
↵
for (ll j = W; j >= c; j--) {↵
dp[j] = max(dp[j], dp[j-c] + val);↵
}↵
cnt -= take;↵
}↵
}↵
~~~~~↵
really nothing fancy we are just doing the splitting and the knapsack together instead of storing every one of the $log_2(freq_i)$ items $n$ times and now the space complexity is $O(W + m)$ ↵
↵
↵
and that's about it for the blog :)↵
thank you very much for reading up till here and please give me your feedback :)↵
if you want me to try and explain another technique, data structure or something tell me or if you want some clarification↵
thx and have a good day <3↵
↵
some problems with that need the optimizations I talked about↵
↵
Binary Splitting↵
- [problem:755F]↵
↵
Bitset↵
- [problem:577B]↵
- [problem:1856E1]↵
↵
↵
↵
↵
↵
