0/1 Knapsack Problem solved using Iterative and Dynamic Programming
Given weights and values(profits) of N items, put these items in a knapsack of max capacity W to get the maximum total value(profit) in the knapsack.
Let's simplify the problem statement:
Assume I am a thief and reached someone's place to rob and there is notbody present at home.
There are so many(say 100) valuable items in the house, If i picked all the items i will become millionaire ... :) but the Sack which I took for putting the items can hold weight max upto 5 Kg.
There are items like
- TV(Weight: 2 Kg, Market Value: 2000)
- Laptop(Weight: 1 Kg, Market Value: 5000)
- Chairs(Weight: 3 Kg, Market Value: 500)
- Table Lamp(Weight: 1 Kg, Market Value: 1000)
- Mirror(Weight: 3 Kg, Market Value: 3000)
- Painting(Weight: 2 Kg, Market Value: 4000)
- Clock(Weight: 1 Kg, Market Value: 3000) etc.
I want to pick items such that weight should not exceed 5 Kg (because that is the max capacity that my Sack can hold) and when I sell items in market, the Profit should be maximum.
I am confused as which Items I should pick so that weight is within 5 kg and I get maximum profit.
Lets understand what is the input and the expected output.
Sample 1:
Input:
int knapsackMaxWeight = 5;
int profit[] = {200, 240, 140, 150};
int weight[] = {1, 3, 2, 5};
Output: Max Profit we get is 440 by choosing item with weight 1 and 3.
Algorithm
One of the way to solve this problem is to try every combination of weight till it reach sack capacity and see in which combination we will get maximum Profit,
Check for profit by including,
- Only Item with weight 1 (Profit = 200)
- Only Item with weight 3 (Profit = 240)
- Only Item with weight 2 (Profit = 140)
- Only Item with weight 5 (Profit = 150)
- Comination of Item with weight 1 and 3 (Profit = 440)
- Comination of Item with weight 3 and 2 (Profit = 380) etc
This leads to generic solution as, check the profit you get either
- By picking the item OR
- By not picking the item.
When you pick the Item, you need to remove it from calculation as you already worked on current item and decrease the knapsack capacity by the weight of the item picked.
When you don't pick the Item, you need to remove it from calculation as you already worked on current item and keep the knapsack capacity as it is as we have not picked the item.
Now let see what value it returns at each recursive step and how we get max profit.
Note:
Problem with approach of trying every combination is repetation of steps as it has overlapped sub problems.
If the the given item weight and profit is ,
Weight[] = {1, 1, 1},
Profit[] = {30, 40, 50},
KnapSackMaxWeigth = 2,
Try to create recursion tree for this, you will see some thing like below, which has repetitive calculation and time complexity for this approach is exponential.
Recursive solution for Knapsack in Java
package javabypatel;
public class KnapsackProblem {
public static void main(String[] args) {
int knapsackMaxWeight = 5;
int profit[] = {200, 240, 140, 150};
int weight[] = {1, 3, 2, 5};
int maxProfit = maximizeProfitRecursive(weight, profit, weight.length, knapsackMaxWeight);
System.out.println(maxProfit);
}
private static int maximizeProfitRecursive(int[] weightArr, int[] profitArr, int currentItem, int knapsackWeight) {
//If either knapsack weight capacity reached 0 or we don't have more items to pick,
//return 0 in either case.
if(knapsackWeight == 0 || currentItem == 0){
return 0;
}
//if weight of current item on which we are working is greater than knapsack remaining capacity,
if(weightArr[currentItem-1] > knapsackWeight){
//then we can't pick current item, keep knapsack remaining
//capacity as it is and try checking next item
return maximizeProfitRecursive(weightArr, profitArr, currentItem-1, knapsackWeight);
}else{
//Here we have 2 choice, we can either pick the item or not to pick.
//So we have to check profit by picking the item and profit by not picking the item
//(obviously keeping weight constraint in mind otherwise picking item will always be beneficial)
//we can pick current item, reduce knapsack remaining capacity by subtracting
//current item weight from knapsack capacity, and check for next item.
int including = profitArr[currentItem-1] + maximizeProfitRecursive(weightArr, profitArr, currentItem-1, knapsackWeight-weightArr[currentItem-1]);
//Check Profit by not picking item, keep knapsack remaining capacity as it is and try
//checking next item
int excluding = maximizeProfitRecursive(weightArr, profitArr, currentItem-1, knapsackWeight);
//Whichever gives us maximium profit, return that.
return Math.max(including, excluding);
}
}
}
Dynamic Programming Approach
In this approach we will use Dynamic Programming to solve Problem.
We will calculate profit earned for each type of input and store results of each calculation.
So that whenever same type of input calculation is required further in Algorithm, no need to calculate it again and we can directly refer to stored result of previous calulation.
We will take a temporary array temp[][] of
- row length as (Number of Items we have)
- column length as (Knapsack capacity)
So what we will do is decompose the problem into smaller problems, solve it and store result.
We will start checking how much items we can pick if Sack capacity is 0,(if Sack capacity is 1, 2 and so on).
Let's start working on one item with weight 1 and Sack capacity as 0.
If we have Sack capacity 0 then we will not able to pick any item(if we have more items, still we will not able to pick any item as sack capacity itself is 0),
So for Column where Sack capacity is 0 all entries are 0, It means if Sack capacity is 0, then no profit can be earned.
Now, our matrix will look as shown below,
Now, We have, Number of Item = 1 with Weight = 1 and Sack capacity = 1
Should we pick this item or not?
Algorithm,
- If (Item weight > Sack capacity),
We cannot pick the item in this case as it is violating the constraint of Max Sack Capacity.
So we will not pick the item in this case and max profit will remain same as profit we got in previous step without working on this item. - If (Item weight <= Sack capacity),
Now there are 2 options open, whether we should pick the item or should not pick it.
What we will do is, Check the profit we can earn by,- Picking the item
- Not picking the item.
Compare profit in both the case and in which ever case the profit is maximum, we will choose that as Max Profit we can get at this Point. (This Max profit we got is either by including the item or excluding it.)
Coming back to our input,
Number of Item = 1 with Weight = 1 and Sack capacity = 1
Item weight is <= Sack Capacity? YES.
So we will pick the item and update the max profit we can get by picking this item,
For profit, we will look at profit array and corresponding profit for item with weight 1 is 200.
So if we have 1 item with Weight 1 and Sack capacity 1, then max profit we get is by choosing the item and profit we get is 200.
After updating value, Matrix will look like below,
Now, We have 1 item to work on with Weight =1 and Sack capacity = 2.
Item weight is <= Sack Capacity? YES.
So we will pick the item and update the max profit we can get by picking this item,
So if we have 1 item with Weight 1 and Sack capacity 2, then max profit we get by choosing the item is 200.
After picking the item, There is still space present in Sack of weight 1, but we have only 1 item to choose, So remaining sack space will be of no use and max profit we get is by choosing 1 item and Max profit is 200.
Also for Sack capacity 3, 4 and 5, and 1 item to choose with weight = 1, we will get max profit as 200 because we have only one item to choose having weight = 1.
After updating value, Matrix will look like below,
Now, we have 2 items to choose, item with weight 1 and item with weight 3.
Sack capacity is 1.
We have already worked on item with weight 1 and sack capacity 1 and max profit we got is 200.
We will now see whether we can add item with weight 3 when sack capacity is 1.
(item weight 3 > Sack capacity 1), So item cannot be picked.
Max Profit we get is by not picking item with weight 3 and Max profit will remain same as profit we got by not including current item 3 and picking item 1 is 200.
Now, we have sack capacity = 2 and 2 items to choose, item with weight = 1 and
item with weight = 3.
We have already calculated max profit which is 200 when sack capacity = 2 and item to choose is 1 with weight = 1.
Now, we need to see, can we add item with weight 3 to sack capacity 2.
(item weight > Sack capacity). YES.
So we will not able to pick item and max profit we can get is by not choosing current item with weight 3 and max profit remain same that is 200 which we got in previous step.
After updating value, Matrix will look like below,
Now we have 2 items, Item with weight 1 and item with weight 3 & Sack capacity 3.
We have already checked Max profit (200) we can get when there is 1 item to choose of weight 1 and Sack capcity 3.
Now we need to check, can we add item with weight 3 to sack capacity 3.
(Item capcity <= Sack capacity)? YES. we can choose the item,
Before choosing the item, we need to see,
- Picking current item that is item with weight 3 will give us maximum profit OR
- Not picking current item will give us maximum profit.
- Profit we get by picking the current item with weight 3.
Profit of item with weight 3 is 240, Also, after picking item with weight 3, there is no additional space remaining to put additional items,
So including item with weight 3 will get us max profit of 240. - Profit we get by not picking the current item with weight 3.
Profit we get by not choosing current item with weight 3 is 200, which we got by looking at profit we got when there was only 1 item of weight 1 and Sack capacity 3.
Max(including item, not including item) = Max(240, 200) = 240.
So max profit which we get when there is 2 items, item with weight 1 and item with weight 3 and Sack capacity 3 is 240 which we got by including the item with weight 3.
After updating value, Matrix will look like below,
Now, we have Sack capacity 4 and 2 items, item with weight 1 and item with weight 3.
We already know the max profit we can get(200) when there is 1 item with weight 1 and sack capacity is 4.
Now, we need to see whether we can pick item with weight 3 when sack capacity is 4.
(item weight <= sack capcity)? YES. we can choose the item,
Before choosing the item, we need to see,
- Picking current item that is item with weight 3 will give us maximum profit OR
- Not picking current item will give us maximum profit.
- Profit we get by picking the current item with weight 3.
Profit of item with weight 3 is 240,
Also, after picking item with weight 3, there is additional space remaining to put additional items with max weight 1(sack capacity - item weight = remaining sack capacity),
(4-3) = 1, it means we have additonal space in sack which can hold max weight of 1.
We have already calculated the profit we can get when Sack capacity is 1 in previous step which is 200.
So when Sack capcity is 4, we can put 2 items, one with weight 3 and one with weight 1 and profit we will get is (weight 3 profit + weight 1 profit ) = (240 + 200) = 440 is total profit we will get in including item with weight 3 and Sack capacity is 4. - Profit we get by not picking the current item with weight 3.
Profit we get by not choosing current item with weight 3 is 200, which we got by looking at profit we got when there was only 1 item of weight 1 and Sack capacity 4.
Max(including item, not including item) = Max(440, 200) = 440.
So max profit which we get when there is 2 items, item with weight 1 and item with weight 3 and Sack capacity 4 is 440 which we got by including the item with weight 3 and item with weight 1.
After updating value, Matrix will look like below,
Similarly we can get max profit as 440 when Sack capcity is 5 and item to choose is 2, item with weigth 1 and item with weight 3.
(item weight <= sack capacity), YES. So we may choose the item or may not based on profit we get.
Picking item with weight 3 will give profit as,
240 + (profit of remaining capacity which is 5-3 = 2)
We already calculated the max profit we can get when Sack capacity is 2 in previous step is 200.
240 + 200 = 440
Not picking item with weight 3 will give profit as 200, which we can see from previous calculation which includes item with weight 1 and not picking item with weight 3.
Max(440, 200) = 440.
After updating value, Matrix will look like below,
Max profit we can get when there is 3 items, item with weight 1, item with weight 3 and item with weight 2 and Sack capacity 1 is 200.
We have already calcultaed Max profit we can get which is 200 when Sack capacity is 1 and there is 1 item of weight 1.
Also, we have calcultaed Max profit we can get which is 200 when Sack capacity is 1 and there is 2 items, item with weight 1 and item with weight 3.
Now, we need to judge whether including item with weight 2, when sack capacity is 1 will increase our profit OR not picking the item with weight 2 will increase our profit.
Look at below picture for calculation, and After updating value, Matrix will look like below,
Max profit we can get when there is 3 items, item with weight 1, item with weight 3 and item with weight 2 and Sack capacity 2 is 200.
Look at below picture for calculation, and After updating value, Matrix will look like below,
Max profit we can get when there is 3 items, item with weight 1, item with weight 3 and item with weight 2 and Sack capacity 3 is 340.
Look at below picture for calculation, and After updating value, Matrix will look like below,
Max profit we can get when there is 3 items, item with weight 1, item with weight 3 and item with weight 2 and Sack capacity 4 is 440.
Look at below picture for calculation, and After updating value, Matrix will look like below,
Max profit we can get when there is 3 items, item with weight 1, item with weight 3 and item with weight 2 and Sack capacity 5 is 440.
Look at below picture for calculation, and After updating value, Matrix will look like below,
Max profit we can get when there is 4 items, item with weight 1, item with weight 3, item with weight 2 and item with weight 5 and Sack capacity 5 is 200.
Look at below picture for calculation, and After updating value, Matrix will look like below,
Max profit we can get when there is 4 items, item with weight 1, item with weight 3, item with weight 2 and item with weight 5 and Sack capacity 2 is 200.
Look at below picture for calculation, and After updating value, Matrix will look like below,
Max profit we can get when there is 4 items, item with weight 1, item with weight 3, item with weight 2 and item with weight 5 and Sack capacity 5 is 400.
Look at below picture for calculation, and After updating value, Matrix will look like below,
Dynamic programming / Iterative solution for Knapsack Problem in Java
package javabypatel;
public class KnapsackProblem {
public static void main(String[] args) {
int knapsackMaxWeight = 5;
int profit[] = {200, 240, 140, 150};
int weight[] = {1, 3, 2, 5};
int maxProfit = maximizeProfit(weight, profit, knapsackMaxWeight);
System.out.println(maxProfit);
}
private static int maximizeProfit(int[] weight, int[] profit, int max) {
int[][] temp = new int[weight.length+1][max+1];
for (int row = 0; row <= weight.length; row++) {
for (int col = 0; col <= max; col++) {
//Represent 0 item OR Sack with capacity 0
if(row==0 || col==0){
continue;
}
//If col represent Sack weight and if it is >= item weight,
//it means item is eligible to be picked.
if(col >= weight[row-1]){
//Checking picking the item will give Max profit or not picking the item will give Max profit.
temp[row][col] = Math.max(profit[row-1]+temp[row-1][col-weight[row-1]], temp[row-1][col]);
}else{
//Sack weight is less than item weight, So can't pick item and Max profit we
//can get at this point is profit we got in previous step by not picking current item
temp[row][col] = temp[row-1][col];
}
}
}
return temp[weight.length][max];
}
}
You may also like to see
Find the number of Islands using DFS.
Given an array of integers. All numbers occur thrice except one number which occurs once. Find the number in O(n) time & constant extra space.
Count number of Bits to be flipped to convert A to B
Count number of Set Bits in Integer.
Check if number is Power of Two.
Find all subsets of a set (Power Set).
Skyline Problem in Java.
Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted
Count trailing zeros in factorial of a number
When to use SOAP over REST Web Service. Is REST better than SOAP?
Tower Of Hanoi Program in Java.
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment