Created
April 20, 2020 19:32
-
-
Save akhr/7282482be870892b43c1ce969b68c042 to your computer and use it in GitHub Desktop.
0/1 Knapsack Implementation using Dynamic Programming Bottom-Up Approach
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* | |
*/ | |
package dp.knapsack_0_1; | |
import static org.junit.Assert.assertEquals; | |
import org.junit.Test; | |
/** | |
* @author ramamurthy | |
* | |
*/ | |
public class Knapsack_0_1_DP_Bottom_Up { | |
/*Bottom up | |
* - NO RECURSION | |
* - Hardcode answers for base cases | |
* - Use a FOR loop - Move from LEAF to ROOT | |
*/ | |
/** | |
* Items A, B, C, D | |
* int[] profits = {1, 6, 10, 16}; | |
* int[] weights = {1, 2, 3, 5}; | |
* Capacity = 7kgs | |
*/ | |
/** | |
* Complete DP Cache - Each cell is the PROFIT | |
* C=0 C=1 C=2 C=3 C=4 C=5 C=6 C=7 | |
* (w 1, p 1) Item1 0 1 1 1 1 1 1 1 | |
* (w 2, p 6) Item2 0 1 6 7 7 7 7 7 | |
* (w 3, p 10) Item3 0 1 6 10 11 16 17 17 | |
* (w 5, p 16) Item4 0 1 6 10 11 16 17 22 | |
*/ | |
public static int solveKnapsack(int[] profits, int[] weights, int capacity) { | |
int n = weights.length; | |
Integer[][] dp = new Integer[n][capacity+1]; | |
/** | |
* Base case only DP Cache | |
* C=0 C=1 C=2 C=3 C=4 C=5 C=6 C=7 | |
* Item 1 0 1 1 1 1 1 1 1 | |
* Item 2 0 | |
* Item 3 0 | |
* Item 4 0 | |
*/ | |
// populate the capacity=0 columns, with '0' capacity we have '0' profit | |
for (int item=0; item<n; item++ ) { | |
dp[item][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]; | |
} | |
} | |
for (int item=1; item<n; item++) { | |
for(int cap=1; cap<=capacity; cap++) { | |
int profit1 = 0; | |
// include the item, if it is not more than the capacity | |
if(weights[item] <= cap) { | |
int newCapacity = cap - weights[item]; | |
profit1 = profits[item] + dp[item-1][newCapacity]; | |
} | |
// exclude the item | |
int profit2 = dp[item-1][cap]; | |
// take maximum | |
dp[item][cap] = Math.max(profit1, profit2);; | |
} | |
} | |
printSelectedElements(dp, weights, profits, capacity); | |
return dp[n-1][capacity]; | |
} | |
/** | |
* Complete DP Cache - Each cell is the PROFIT | |
* C=0 C=1 C=2 C=3 C=4 C=5 C=6 C=7 | |
* (w 1, p 1) Item1 0 1 1 1 1 1 1 1 | |
* (w 2, p 6) Item2 0 1 6 7 7 7 7 7 | |
* (w 3, p 10) Item3 0 1 6 10 11 16 17 17 | |
* (w 5, p 16) Item4 0 1 6 10 11 16 17 22 | |
*/ | |
private static void printSelectedElements(Integer[][] dp, int[] weights, int[] profits, int capacity) { | |
int n = weights.length; | |
int totalProfit = dp[n-1][capacity]; | |
for(int item=n-1; item>0; item--) { | |
if(dp[item-1][capacity] != totalProfit) { | |
//then this item is included. | |
System.out.println("Included Item - "+weights[item]); | |
capacity -= weights[item]; | |
totalProfit -= profits[item]; | |
} | |
} | |
if(totalProfit != 0) | |
System.out.println("Included Item - "+weights[0]); | |
} | |
@Test | |
public void Test_01() { | |
int[] profits = {1, 6, 10, 16}; | |
int[] weights = {1, 2, 3, 5}; | |
int capacity= 7; | |
int expected = 22; | |
assertEquals(expected, solveKnapsack(profits, weights, capacity)); | |
} | |
@Test | |
public void Test_02() { | |
int[] profits = {1, 6, 10, 16}; | |
int[] weights = {1, 2, 3, 5}; | |
int capacity= 6; | |
int expected = 17; | |
assertEquals(expected, solveKnapsack(profits, weights, capacity)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment