stefdasca's blog

By stefdasca, history, 4 years ago, In English

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.

Here is the video

As always, if you have constructive feedback, please share it in comments or in the Discord server.

Thanks for watching.

  • Vote: I like it
  • +95
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Hi sir, i am new to CP. How can I be better

I'm your big fan :D

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Please, replace the discord link in youtube video. It is not working.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

question
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.