Time Complexity: O(n x c) where n is the number of items and c is the capacity of the bag.

Space Complexity: O(n x c)

So, let us start with the dynamic programming solution in three stages:

1. Storage and Meaning:
   So, we have two arrays. One is filled with the weights and the other is filled with the cost of that much weight of the items as shown in the image:
   This means that the 0^th item's 2 units weight has a price of 15 units and so on. Let us say the maximum capacity of the bag is 7. So, the dp matrix will look like this:
   At the columns, we have kept the capacity of the bag increasing from 0 to the maximum capacity given to us i.e. 7. At the rows, we have kept the weight and price of the items. The cross in the row is depicting the situation that no item is given to us.
   So, each cell in the matrix represents the max price of the bag when the capacity of the bag is equal to the current column number and the items till the current row number are given to us.
2. Direction of Solving:
   When there is no item given to us, then the bag will always remain empty whatever the capacity of the bag may be. So, the 0^th row will have all the values 0 in it.
   When the capacity of the bag is 0, the price will be 0 as whatever the items may be, we cannot put any item in the bag. So, the 0^th column will have all the values 0 in it.
   
   Therefore, the smaller problem starts from the 0^th row and the 0^th column and increases when we move along in the matrix. So, the direction of solving is clear. We will solve from the start to the end of the matrix row-wise.
3. Travel and Solve:
   We hope that you have seen the 0-1 KNAPSACK problem video in the foundation course and know how we used to fill this matrix with the help of analogy of this 0-1 Knapsack problem to a one-day cricket match. So, let us do the same again quickly.
   1^st Row: So, in the first row, we have only one weight available to us and i.e. 2. So, the bag can either be empty or its weight can be 2. If the max capacity of the bag is less than 2(which is represented by the current column number), the value at dp[i][j] will be 0 where i=1 and j<2. Value at dp[1][2] will be 15 i.e. the price of 2 units weight and there is no other weight further so dp[i][j] will remain 15 for all i=1 and j>=2.
   
   2^nd Row: As discussed above, the value at dp[i][j] when j<2 will remain 0 i.e. the values are copied from the previous row. Why? Think!!! After this, we reach dp[2][2]. So, we will put 15 as we have a weight of 2 which does not violate the bag capacity and gives the highest price.
   After this, when j=3 and 4, we will still have dp[i][j]=15 i.e. the cost of weight 2 as the second weight 5 cannot be accommodated.
   When we are at dp[2][5], we have two options. Either we can put 5 and the bag will become full and the cost will be 14 or we can put 2, the bag will not be full and the cost will be 15. So, in both cases, the capacity of the bag is not violated. So, we will see the higher price i.e. 15 for the weight 2. So, we will insert 15 in dp[2][5] and further till we reach dp[2][7].
   At dp[2][7], if we only insert 2, the capacity is not violated and the cost is 15. If we insert only 5, the capacity of the bag(7) is still not violated and the cost is 14. If we put both 2 and 14, the capacity of the bag is not violated and we get a cost of 29. So, we will put both the weights and dp[2][7]=29.
   So, we can fill the entire matrix in this way. We need to remember the following steps while inserting an element into the matrix:
   
   1. If the current capacity of the bag is less than the current item's weight, copy the elements from the previous row.
   2. If the current capacity of the bag is equal to the current item's weight, compare the price of the current item with dp[i-1][j] i.e. the price kept for the same capacity in the previous row and insert the maximum among them into dp[i][j].

What about the point when the current capacity becomes greater than the current item's weight? This is a tricky one right? Well, you have already solved this problem previously so we leave this as a challenge for you.

Dear reader, we request you keep the above points in mind and fill the matrix. The filled dp matrix is shown below:

We hope that you have understood the procedure till here. If you have any doubts, refer to the solution video to clear all of them. Now, let us move to the second part of this question. How will we print all the answers?

So, we will again use the same Breadth-First Search of a Graph technique that we have been using in the previous questions in this series as well.

You know what we will do, right? Yes, we will take a queue and use the BFS of a graph.

We will have a queue of pairs that will contain the custom class pairs which tell us about the location of the element and the path so far. So, initially, the queue will contain one pair whose location will be the last element of the matrix i.e. row=items.length and col=capacity.

Have a look at the image shown below:

The price of the bag can be 75 with or without including the last weight of 4 units as well. In this case, if we would have got the price without including the 4 units weight, the value at dp[i-1][j] would have also been 75. But, this is not the case since the price has become 75 by adding the weight of 4 units.

So, we will remove the front element of the queue and add the new element and that element is shown in the image:

The numerator shows the location i.e. the 4^th row and the 3^rd column and the denominator shows the index at which the weight of 4 units is present in the weights array.

Note: Dear reader, do not confuse the 4 written in the denominator with the weight 4. It is the index at which the weight that has been included is present in the weights array.

What do we mean by this? See, the price 75 could have been made with or without including the weight of the item at index 4. So, what would we have done if price 75 could have been achieved both with including and without including this weight?

If this would have been the case, then the value at dp[i-1][j] i.e. dp[n-1][[capacity] i.e. dp[4][7] would have also been 75 and we would have included both of them in the queue.

But this is not the case. So, let's come back to our question.

At dp[4][3], we have a price of 45 that can be completed with or without including the weight at index 3 as well. Since dp[i-1][j] i.e. dp[3][3] is not equal to 45, the weight was included which resulted in a price of 45. Since the weight is 3 units, we include 3 units and the remaining capacity becomes 0 i.e. we have reached column 0. Hence we will stop now.

Now, we will print whatever the path soo far is there in the pair left in the queue and this is our answer.

So, if we include the index 4 and index 3 weight then we will get the maximum cost and the capacity of the bag will also not be violated.

So, dear reader, we hope that you have understood the complete procedure. We request you refer to the complete solution video once to understand the procedure completely and the code written below too. Also, the solution video discusses how to maintain the order while printing as we got the index 4 and 3 in our path so far above whereas we have to print index 3 before index 4. So, do check the video out.