DP - Knapsack

Question 1

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 –

Answer 1

Pseudo code:

1. Declare 2D matrix where row and col size will be weight size plus 1.
2. Row represents weight and profit.
3. Col represents capacity.
4. With zero profit and any amount of capacity max profit is zero, so we will initialize all cols on zeroth row with zero value.
5. With zero capacity, we can get max zero profit so we will initialize all rows on zeroth col with zero value.
6. 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];
	}