0 - 1 knapsack

A knapsack is a bag with straps, usually carried by soldiers to help them take their necessary items or valuables during their journey. Each item has a value and definite weight attached to it. So, the soldier has to pick the most valuable items within their maximum weight limit as they cannot put everything in their bag. The word 0/1 means that either we can take it or leave it. We cannot take an item partially. This is known as the famous 0-1 knapsack problem. We will take the bottom-up approach for solving the 0-1 knapsack problem. Here is the pseudocode for the solution:

Procedure knapsack(n, W, w1,...,wN, v1,...,vN) 
for w = 0 to W 
    M[0, w] = 0 

for i = 1 to n 
    for w = 0 to W 

    if wi > w : 
        M[i, w] = M[i-1, w] 
    else : 
        M[i, w] = max (M[i-1, w], vi + M[i-1, w-wi ]) 
return M[n, W] 

end procedure  

For example, if we have five items, ...