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!
2 Likes
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.
2 Likes
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. 
5 Likes
Get yourself familiar with standard dp problems and some modifications. Constraints also helps a lot in identifying dp problems.
3 Likes
Tnx a lot
Yup the question was actually nice! Thanks Shivam
Or you can use a different approach.
2 Likes
loved your BFS approach brother. Thnx a lot