### TimberLee's blog

By TimberLee, history, 5 years ago, I recently read somewhere that some DP solutions like knapsack can be optimised and the overall complexity can be reduced by a factor of 32 using std::bitset in C++.

Can someone explain this optimisation and the kinds of DP on which this works ? Comments (15)
 » Another Problem using this trick.
 » 5 years ago, # | ← Rev. 3 →   Hi !Problem is: we have n numbers, calculate how many distinct numbers we can form by sum some of these numbers.For example if we have set {17, 23, 40}, we can form {0, 17, 23, 40, 57, 63, 80}.Dp solution is obvious: dp = 1; for(int i = 0; i < n; i++) for(int j = maxv - 1; j >= a[i]; j--) // maxv is some number bigger than sum of a[i]'s dp[j] |= dp[ j - a[i] ]; cout << count(dp, dp + maxv, 1) << '\n'; Now how to optimize it? bitset can store bits and do operations 32 times faster like this: bitset dp; dp.set(0); for(int i = 0; i < n; i++) dp |= dp << a[i]; cout << dp.count() << '\n'; Good problem (and hot!) to solve: SnackDown 2016 Online elimination round » Robot Walk.
•  » » Can you explain why exactly using bitset is O(N / 32). I tried looking it up but couldn't find any exact reasons.I tried to read the library implementation of bitset(from usr/include/bitset) and it appears to be O(N) only(or O(maxv) from your code). This is the implementation on my system(G++ 4.9.2) void _M_do_or(const _Base_bitset<_Nw>& __x) { for (size_t __i = 0; __i < _Nw; __i++) _M_w[__i] |= __x._M_w[__i]; } And _Nw is defined in template struct _Base_bitset so basically it makes O(maxv) operations only. The functions xor and and also seem to be implemented similarly. How is this faster than normal looping?
•  » » »  template class bitset : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> So _Nw = _GLIBCXX_BITSET_WORDS(maxv) = maxv/32 (on a 32-bit system)
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   Ah nice I seemed to mix up the definitions of _Base_bitset and bitset. So now we basically have an N digit binary number split into groups of size 32 and dealt with individually. Is that understanding right?