Hello everybody!
Since it has been suggested by many people in my Discord server, I decided to create a longer and more detailed video tutorial about the Knapsack problem.
Because there are many such tutorials online, I have also added more advanced Knapsack variations, including different types of tricks and usages of this DP technique in the problems.
As always, if you have constructive feedback, please share it in comments or in the Discord server.
Thanks for watching.
Hi sir, i am new to CP. How can I be better
I'm your big fan :D
I highly recommend this tutorial to all Experts and under, it's a very nice introduction to knapsack DP, plus some of the problems that Stef shows are quite interesting!
The "log2 trick" was my suggestion, I learned it quite late (as a CM), and I think it's one that isn't covered in detail much elsewhere.
And with that I say
stefdasca orz
this and this are also very rare trick
Please, replace the discord link in youtube video. It is not working.
Thank you for observing that!
stefdasca hello this is the question bothering me from long time, can you at least tell me, is this even solvable given the constraints of question.
Is there any greedy or randomised approach to this question which is very less likely to give error.
If I understand statement correctly (image doesn't contain any full sample tests) — solution is greedy.
Sort blocks by height in decreasing order. Now take the largest blocks until their sum is $$$\ge$$$ than $$$H$$$.
It could be easily proven next way: imagine you have array $$$max_k$$$ — maximal sum of heights of some $$$k$$$ blocks $$$(0 \le k \le n, max_0 = 0)$$$. It's obvious that $$$max_k$$$ is sum of $$$k$$$ largest blocks. And answer for problem is such number $$$j$$$ that $$$max_{j - 1} < H \le max_j$$$ — exactly what would you get by greedy approach.
Won't it fail on simple test case for array [6,7,8,9], and H = 22 by your method will end up to 9+8 = 17, then you will never get 5 to reach 22, but {6,7,9} as subset exists which give sum 22.
By any means are you trying to say that for existence of solution we can use bitset in c++, then estimate of minimum cardinality of subset can be done by some greedy way.
As I mentioned before — absence of sample tests on image could cause incorrect understanding of problem.
Problem with "exactly $$$H$$$" is really knapsack problem and has next solution:
$$$dp[i][j]$$$ — minimal number of blocks, taken from blocks $$$1 \dots i$$$, and total height of taken blocks is $$$j$$$ $$$(0 \le i \le n, 0 \le j \le H)$$$.
Formulas are usual for knapsack:
$$$dp[i][j]$$$ = $$$min(dp[i-1][j], dp[i-1][j-a_i] + 1)$$$
And complexity of that approach is $$$O(N \cdot H)$$$ with $$$O(H)$$$ memory.
Given constraints from photo $$$0 < N, H < 10^6$$$ I don't see any way to solve that problem by knapsack approach.
So are you sure that problem is "build tower with height exactly $$$H$$$", not " at least $$$H$$$ "?
And could you provide link to the problem statement and/or all sample tests from statement?
Yes its knapsack with subset sum = H not sum >= H, yeah I think the question is wrong. Or wrong constraints. Source of the problem was someone's hiring challenge question few months ago, someone asked me it on telegram.