Knapsack top down dynamic programming using java
Categories: Java Java Examples Dynamic programming/Recursion
package dynamic.programing.knapsack;
import java.util.Iterator;
public class KnapsackTopDownDynamicProgramming {
// Knapsack top down dynamic programming using java
public static void main(String[] args) {
int[] wt = new int[] { 1, 3, 5 };
int[] val = new int[] { 100, 20, 75 };
int weight = 9;
int length = wt.length;
System.out.println("Recurcive Max value : " + knapsackDP(wt, val, weight, length));
System.out.println("Dynamic Progamming Max value : " + knapsackDP(wt, val, weight, length));
}
static int knapsack(int wt[], int val[], int w, int n) {
// Recursive programming
if (w == 0 || n == 0)
return 0;// dp[n+1][w+1] for w=0 and n=0 return 0-initialization of dp[n][0] and dp[0][w]
// array.
if (wt[n - 1] <= w)
// choose max value and add to matrix dp[][] index
return Math.max(val[n - 1] + knapsack(wt, val, w - wt[n - 1], n - 1), knapsack(wt, val, w, n - 1));
else if (wt[n - 1] > w)
// skipped if wt[n-1] great then weight;
return knapsack(wt, val, w, n - 1);
return -1;
}
static int knapsackDP(int wt[], int val[], int w, int n) {
// Dynamic programming
int dp[][] = new int[n + 1][w + 1];
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < w + 1; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
}
}
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < w + 1; j++) {
if (wt[i - 1] <= j) {
dp[i][j] = Math.max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][w];
}
}