Subset Sum Problem SubSet Sum Problem Solution using Knapsack
Categories: Java Java Examples Dynamic programming/Recursion
package dynamic.programing.knapsack;
public class SubsetSumProblemKnapsack {
//Subset Sum Problem-SubSet Sum Problem Solution using Knapsack
public static void main(String[] args) {
int arr[] = new int[] { 1, 4, 3 };
int sum = 0;
int length = arr.length;
System.out.println("Sub Set Sum Problem Solution using Knapsack :" + subSetKnapsack(arr, sum, length));
System.out.println("Sub Set Sum Problem Solution using Knapsack :" + subSetKnapsackDP(arr, sum, length));
}
private static boolean subSetKnapsack(int[] arr, int sum, int n) {
//
if (sum == 0)
return true;
if (n == 0)
return false;
if (arr[n - 1] <= sum)
return subSetKnapsack(arr, sum - arr[n - 1], n - 1) || subSetKnapsack(arr, sum, n - 1);
else
return subSetKnapsack(arr, sum, n - 1);
}
private static boolean subSetKnapsackDP(int[] wt, int s, int n) {
boolean dp[][] = new boolean[n + 1][s + 1];
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < s + 1; j++) {
if (i == 0 )
dp[i][j] = false;
if (j == 0)
dp[i][j] = true;
}
}
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < s + 1; j++) {
if (wt[i - 1] <= j) {
dp[i][j] =dp[i - 1][j - wt[i - 1]] || dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][s];
}
}