0/1 Knapsack: Algorithm, Explanation and Code;

0/1 Knapsack: Algorithm, Explanation and Code;

Problem Statement: Given a set of items, each with a "weight" and a "value", determine the number of each item to include in a collection/knapsack, so that -> "the total weight is less than or equal to a given limit" and "the total value is as large as possible"

Explanation:
The value and the weight/cost of each item is given in the arrays val[] and wt[] respectively.
The nth item has value val[n] and weight wt[n]; The total capacity of knapsack is W
The solution is simple. Let dp[n][w] be the optimal value for the first n items with total value w. Now the next task would be to define dp[n][w] in terms of smaller subproblems, in terms of some recursive formula.
Consider the case in which the weight/ cost of the item is greater than the total capacity of knapsack.(i.e. w[n] > Total ) Since the current item exceeds the capacity of the knapsack, all we can do here is to ignore the item move to next item in the array.
Now, if the weight of the item is less than or equals to the total capacity of the knapsack, we'll have two choices:
we can either choose the item or not and move to next item. since we want maximum profit so we will have to go with the choice which gives us more profit.
If we choose the item, then we will have to decrease the capacity of knapsack by the weight of the current item.
If we don't choose the item then we will continue to next item with capacity of knapsack unchanged.
The first case is DP[n,w] = DP[n−1, w]. if wt[n] > W, meaning the n'th item weighs more then are target weight so it cannot be added even if the knapsack is empty.
The second case is the decision case, DP[n, W] = MAX( DP[n−1, W ], DP[n−1, W−wt[ n-1 ] ]+val[n-1] ) it means that either we don't add Item n to our set, in which case our best so far is DP[n−1,W], or we do add it, in which case we only have W−wt[n] weight remaining to be filled with items 1 to n-1 and our total value is DP[n−1,W−wt[n-1] ]+val[n-1], which is our recursive value plus the value of the new Item.

Algorithm (Iterative) :
# Given: val[n] --value array, wt[n] -- weight/cost array, W -- capacity of bag/knapsack;
(I) Initialize the first row and the first column of DP[][] array with zeros.
(II) Iterate through DP[][] array.
(III) For each DP[i][j] :
if j <= W then DP[I][j] = max( val[i-1] + DP[i-1][j-wt[i-1] , DP[i-1][j] );
else DP[I][j] = DP[i-1][j];
(IV) return DP[n][W];

Sample Problem: https://www.spoj.com/problems/KNAPSACK/
Solution code: