0/1 Knapsack is based on the famous problem with the same name which is efficiently solved using Dynamic Programming. We will go through a set of problems to develop an understanding of DP.
We will always start with a brute-force recursive solution to see to see the overlapping subproblems. Then we will modify our algorithm to apply advanced Memoization and Bottom-Up Dynamic Programming to develop a complete understanding.
Given two integer arrays to represent weights and profits of ’N’ items, we need to find a subset of these items which will give us maximum profit such that their cumulative weight is not more than a given number ‘C.’ Each item can only be selected once, which means either we put an item in the knapsack or we skip it.
Items: { Apple, Orange, Banana, Melon }
Weights: { 2, 3, 1, 4 }
Profits: { 4, 5, 3, 7 }
Knapsack capacity: 5Apple + Orange (total weight 5) => 9 profit
Apple + Banana (total weight 3) => 7 profit
Orange + Banana (total weight 4) => 8 profit
Banana + Melon (total weight 5) => 10 profitThis shows that Banana + Melon is the best combination as it gives us the maximum profit, and the total weight does not exceed the capacity.
A basic brute-force solution could be to try all combination of the given items, allowing us to choose the one with maximum profit and a weight that doesn’t exceed C.
