Knapsack

Complexity: Polynomial time - O(sum * number of elements)

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

Points to remember:

• We need to initialize the initial value as zero.
• Scale up the value of the dp array by so that we do not have out of bounds exception
• The max value of the knapsack is always compared with the value with the one having same sum and with lesser element.