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 - 755F - PolandBall and Gifts

Bitset - 577B - Modulo Sum - 1856E1 - PermuTree (easy version)

EDIT: still haven't finished the sheet yet so stay tuned but you can think about the three problems provided :)