Dynamic Programming Question: 0-1 Knapsack problem

0-1 Knapsack problem is a very classic example of dynamic programming.
PROBLEM STATEMENT:Given an array of items with their quantity and their values, determine the maximum value of the items that can fit into the bag with a capacity of W.

SOLUTION:
An important thing to keep in mind about such question is that here we cannot take the fraction of any item, it is either whole or nothing at all.
This question can be solved with the help of dynamic programming. In fact, this question is a classic question of dynamic programming.
ALGORITHM:

1. We have been given a list of items with their value and weights.
2. Here we use the concept of dynamic programming, that is, we store the results of the previous calculations in an array and using those results for further calculations. 3.We start our calculations from the nth item. Here we check whether the weight of the nth item is less than the weight of the knapsack.If the weight of the knapsack is greater than the weight of the item , then we have two options, we can either include that item or we can exclude that item from our chosen ones. As we have been asked to store the maximum, therefore, we choose the maximum of the two.
3. If the weight of the knapsack is less than the weight of the item there is no way we can include that item.
4. We continue this process from the nth item to the 1st item.

CODE:

Hope this post helps you in becoming a better competitive programmer. Follow my Github for more competitive programming questions