Can someone please help me with the intuition of the editorial of Watching CPL. Why did we think of 0-1 Knapsack and how did we reach to the solution which was finally provided?! I am stuck on the thought that can’t we have an easier approach than this?! I am unable to understand how we reached to this solution!
because there was choice to either include or exclude the boxes (Not partially, as splitting of boxes is not allowed) and we also had to optimize (minimize) the number of boxes getting used.
Let’s rephrase the question a bit(with some modifications): We are given a bag of size k and we need to fill it with balls of weight w_i . What is the minimum/maximum balls required?.
Statements like these follow are standard knapsack problems. The only modification here was that we needed to fill 2 “bags” and the weights were not fixed to exactly k but “atleast k”. The motive of WIPL was to make it educative for beginners. Make sure to checkout the official editorial.
Get yourself familiar with standard dp problems and some modifications. Constraints also helps a lot in identifying dp problems.
Tnx a lot
Yup the question was actually nice! Thanks Shivam
loved your BFS approach brother. Thnx a lot