Compression state DP bit operation

I brushed a little video while writing this blog , Today, all provinces and cities have basically given out scores , Then I think this year's question should be very difficult , There is a sentence in the comment area that makes me feel good ,“ At least we should give ordinary people a way to live ”, alas … It's tragic , Okay , Gossip and less narration , Direct to the point ！
Today I wrote a Luogu , The current state is that there is no idea without looking at the problem solution , I have to write for more than an hour ,（ I'm too fond of vegetables.
subject ：
https://www.luogu.com.cn/problem/P1441

But today I have a train of thought without looking at the solution , I did a similar problem yesterday , Result timeout + The answer is partly correct , Send , In desperation, I turned to the problem solving area , I want to post one first Code , When I saw this , I was wondering why 100 Code to line , You can finish it in ten lines , Even more , alas

#include <bitset>
#include <cstdio>
int w[25];
int table[16] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
int popcount(unsigned int x) {
     //  return x In binary 1 The number of 
    int ret = 0;
    for(int i = 0; i < 8; i++) ret += table[x & 15], x >>= 4;
    return ret;
}
int main() {
    
    int n, m, ans = 0;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", w + i);
    for(int i = 0, li = 1 << n; i < li; i++) {
    
        if(popcount(i) == n - m) {
    
            std::bitset<2010> S;
            S[0] = 1;
            for(int j = 0; j < n; j++) if(i & (1 << j)) S |= S << w[j];
            int siz = S.count();
            ans = ans > siz ? ans : siz;
        }
    }
    printf("%d\n", ans - 1);
    return 0;
}

The source of the above code ：https://www.luogu.com.cn/problem/solution/P1441,pantw For the author
He calculated the number of digits skillfully , But it should be the regular operation of the boss .
The focus is still on the cycle
The most important thing about him is this sentence ：

if(i & (1 << j)) S |= S << w[j];

What do you mean , We can think about the complete knapsack problem , The following is the weight of the backpack , This is also , He takes and as the subscript , Then use the bit operation to mark , For example, the following example ：

3 1
1 2 2

Obvious , I'm taking out 2 after 1 and 2 It can make up 1,2,3 So the output is 3
At this moment , If the original bit is S[0]=1,S[1]=1（ Only 1 a number ） Then add in one 2, Use the above operation , speak S Move two bits to the left and match the original S Phase or , In this way, it becomes S[0]=1,S[1]=1,S[2]=1,S[3]=1, May use questions , What if the added number coincides with the original number ? Very simple, for example , The original state is S[0]=1,S[1]=1,S[3]=1 Add in one 2 after S and S[2]=1,S[3]=1,S[5]=1 Phase or , In this way, it is 0,1,2,3,5 yes 1, Two 3 Or it becomes a
An inappropriate method ： It's my way , The reason why I have ideas , Because I have done a very similar problem before this problem
https://www.luogu.com.cn/problem/P3694
It is used here dp It's done , That is, the previous state accumulation , Then the back state comes from the front .（ But they all use bit operations , The shell is the same
But this method has one drawback , When you count again , It is necessary to know which numbers are added before and have appeared , These should be deleted , So we need to use vectors to record ,（ My array , If you want to use bit operations, you have to 2000 Many bits , stay int Only 32 In the case of bit , Let's pull it down .
So the big guy's solution is not bad , Not pure dp, But the method is ingenious .