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*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(N*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