DP - Knapsack Flashcards
1
Q
Knapsack
Given the weights and profits of ‘N’ items, we are asked to put these items in a knapsack which has a capacity ‘C’. The goal is to get the maximum profit out of the items in the knapsack. Each item can only be selected once, as we don’t have multiple quantities of any item.
Let’s take the example of Merry, who wants to carry some fruits in the knapsack to get maximum profit. Here are the weights and profits of the fruits:
Items: { Apple, Orange, Banana, Melon }
Weights: { 2, 3, 1, 4 }
Profits: { 4, 5, 3, 7 }
Knapsack capacity: 5
TC –
SC –
A
Pseudo code:
- Declare 2D matrix where row and col size will be weight size plus 1.
- Row represents weight and profit.
- Col represents capacity.
- With zero profit and any amount of capacity max profit is zero, so we will initialize all cols on zeroth row with zero value.
- With zero capacity, we can get max zero profit so we will initialize all rows on zeroth col with zero value.
- Loop throw row with 1st index, col with 1st index.
i) If weight on ith index less than or equal to capacity on jth index, sum up profit on ith index and (previous row, col will be (capacity minus weight on ith index)).
ii) Else profit will be previous row and jth col.
iii) Store the max profit from point 6-i & 6-ii into dp[i][j].
public int solveKnapsack(int[] profits, int[] weights, int capacity) { // base checks if (capacity <= 0 || profits.length == 0 || weights.length != profits.length) return 0;
int n = profits.length; int[][] dp = new int[n][capacity + 1];
// populate the capacity=0 columns, with '0' capacity we have '0' profit for(int i=0; i < n; i++) dp[i][0] = 0;
// if we have only one weight, we will take it if it is not more than the capacity for(int c=0; c <= capacity; c++) { if(weights[0] <= c) dp[0][c] = profits[0]; }
// process all sub-arrays for all the capacities for(int i=1; i < n; i++) { for(int c=1; c <= capacity; c++) { int profit1= 0, profit2 = 0; // include the item, if it is not more than the capacity if(weights[i] <= c) profit1 = profits[i] + dp[i-1][c-weights[i]]; // exclude the item profit2 = dp[i-1][c]; // take maximum dp[i][c] = Math.max(profit1, profit2); } } // maximum profit will be at the bottom-right corner. return dp[n-1][capacity]; }