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 :-
Unbounded 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 accommodated using 1 or
more instances of given weights.
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 17. We can use one or more instances of any items to fill the knapsack such that the value that can be accommodated in the knapsack is maximized.
We see that, if we pick up 5 instances of weight 3 & 1 instance of weight 2,
we can accommodate a total value of 550 which is the maximum value that can be collected using the given weights, keeping in mind the constraint that knapsack weight is 17.

Solution :-
We will maintain an array knapsack [ W + 1 ] where ' j ' index stores the maximum value that can be fitted in a knapsack of capacity ' j '.
Then, knapsack [ W ] gives the maximum value that can fitted in the knapsack of given weight i.e ' W '.
Let us find the structure of the optimal solution.
Let knapsack ( j ) denotes the maximum value that can be fitted in a knapsack of weight ' j '.
While computing knapsack ( j ), we need to decide whether to select or reject an instance of a weight ' i '.
If we reject all the weights, then knapsack ( j ) = knapsack ( j - 1 ) and
If we select an instance of weight ' i ', then
knapsack ( j ) = maximum [ knapsack ( j - W ( i ) ) + V ( i ) for i = 0, ... , n - 1 ]
Thus, the structure of the optimal solution is defined recursively as :
knapsack [ j ] = max ( knapsack [ j - 1 ] , { knapsack [ j - w [ i ] ] + v [ i ] for i = 0...n-1 } )
Finally, knapsack [ W ] gives the required solution. In the implementation below, we maintain some additional information to print the selected weights and their no. of instances apart from the maximum value that can be accommodated in the given knapsack.