The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. ― Donald E. Knuth

# Algorithms

## Dynamic Programming

Problem :-
0 / 1 Knapsack problem.
Given a set of 'n' items having weights { W1,W2,W3,.....,Wn } & values { V1,V2,V3,.....,Vn }
and a Knapsack of weight W, find the maximum value that can be accomodated using maximum
1 instance of each weight i.e we can either pick that weight or leave it.
So, the aim is to maximize the value of picked up items such that sum of the weights is less than
or equal to W ( Knapsack Weight ).
Consider 3 items having weights { 2, 3, 5 } & values { 50, 100, 140 }.
We have a Knapsack of weight 5. We can either pick up a weight or leave it.
We see that, if we pick up weight 2 & weight 3,
we can accomodate a total value of 150 which is the maximum value that can be collected using the given weights, keeping in mind the constraint that knapsack weight is 5.

Solution :-
We will maintain a 2D array knapsack [ n + 1 ][ W + 1] where knapsack [ i ][ j ] stores the maximum value that can be accomodated in a knapsack of weight ' j ' using first ' i ' weights. Then, knapsack [ n ][ W ] gives the maximum value that can be fitted in the knapsack of given weight ' W ' using the given ' n ' weights.
Let us determine the structure of the optimal solution.
Let knapsack [ i ][ j ] denotes the maximum value that can be fitted in the knapsack of capacity ' j ' using first
' i ' weights.
We can either select or reject a particular weight.
If the ith i.e w ( i ) is greater than knapsack capacity W, then knapsack [ i ][ j ] = knapsack [ i - 1 ][ j ]
else there are two possible cases :
1 ) Reject the weight ' i ' : knapsack [ i ][ j ] = knapsack [ i - 1 ][ j ]
2 ) Select the weight ' i ' : knapsack [ i ][ j ] = knapsack [ i - 1 ][ j - w ( i ) ] + v ( i )
Since, we want to maximize the value accomodated in the knapsack, we need to consider the maximum of the two cases. Thus, the structure of the optimal solution defined recursively as :
knapsack [ i ][ j ] = max (    knapsack [ i - 1 ][ j ] , knapsack [ i - 1 ][ j - w ( i ) ] + v ( i )    )
Finally, knapsack [ n ][ W ] gives the required solution. See the implementation below.