AD2 Lab
Breadth-First Search (BFS)
import java.util.*;
class BFS {
private int V;
private LinkedList adj[];
BFS(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void BFS(int s) {
boolean visited[] = new boolean[V];
LinkedList queue = new LinkedList();
visited[s] = true;
queue.add(s);
while (queue.size() != 0) {
s = queue.poll();
System.out.print(s + " ");
Iterator i = adj[s].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
public static void main(String args[]) {
BFS g = new BFS(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("Following is Breadth First Traversal " +
"(starting from vertex 2)");
g.BFS(2);
}
}
Depth-First Search (DFS)
import java.util.*;
class DFS {
private int V;
private LinkedList adj[];
DFS(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void DFSUtil(int v, boolean visited[]) {
visited[v] = true;
System.out.print(v + " ");
Iterator i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n])
DFSUtil(n, visited);
}
}
void DFS(int v) {
boolean visited[] = new boolean[V];
DFSUtil(v, visited);
}
public static void main(String args[]) {
DFS g = new DFS(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("Following is Depth First Traversal " +
"(starting from vertex 2)");
g.DFS(2);
}
}
Minimum Spanning Tree (MST)
class PrimsAlgo
{
private void primMST(int[][] graph)
{
int V = graph.length;
int[] parent = new int[V];
int[] key = new int[V];
boolean[] mstSet = new boolean[V];
for (int i = 0; i < V; i++) {
key[i] = Integer.MAX_VALUE;
mstSet[i] = false;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++)
{
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++) {
if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v])
{
parent[v] = u;
key[v] = graph[u][v];
}
}
}
printMST(parent, graph);
}
private void printMST(int[] parent, int[][] graph)
{
System.out.println("Edge \tWeight");
for (int i = 1; i < graph.length; i++) {
System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
}
}
private int minKey(int[] key, boolean[] mstSet)
{
int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 0; v < key.length; v++) {
if (mstSet[v] == false && key[v] < min) {
min = key[v];
min_index = v;
}
}
return min_index;
}
public static void main(String[] args)
{
int graph[][] = new int[][] { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
PrimsAlgo t = new PrimsAlgo();
t.primMST(graph);
}
}
Shortest Path using Dijkshtra's Algorithm
import java.util.*;
class ShortestPath {
static final int V = 9;
int minDistance(int dist[], Boolean sptSet[]) {
int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min) {
min = dist[v];
min_index = v;
}
return min_index;
}
void printSolution(int dist[], int n) {
System.out.println("Vertex Distance from Source");
for (int i = 0; i < n; i++)
System.out.println(i + " \t\t " + dist[i]);
}
void dijkstra(int graph[][], int src) {
int dist[] = new int[V];
Boolean sptSet[] = new Boolean[V];
for (int i = 0; i < V; i++) {
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] != 0 &&
dist[u] != Integer.MAX_VALUE &&
dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist, V);
}
public static void main(String[] args) {
int graph[][] = new int[][] {
{ 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }
};
ShortestPath t = new ShortestPath();
t.dijkstra(graph, 0);
}
}
Belman Ford
class BellmanFord
{
class Edge {
int src, dest, weight;
Edge() {
src = dest = weight = 0;
}
}
int V, E;
Edge edge[];
BellmanFord(int v, int e) {
V = v;
E = e;
edge = new Edge[e];
for (int i = 0; i < e; ++i)
edge[i] = new Edge();
}
void BellmanFord(BellmanFord graph, int src) {
int V = graph.V, E = graph.E;
int dist[] = new int[V];
for (int i = 0; i < V; ++i)
dist[i] = Integer.MAX_VALUE;
dist[src] = 0;
for (int i = 1; i < V; ++i) {
for (int j = 0; j < E; ++j) {
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (int j = 0; j < E; ++j) {
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println("Graph contains negative weight cycle");
return;
}
}
printArr(dist, V);
}
void printArr(int dist[], int V) {
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; ++i)
System.out.println(i + "\t\t" + dist[i]);
}
public static void main(String[] args) {
int V = 5;
int E = 8;
BellmanFord graph = new BellmanFord(V, E);
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = -1;
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 4;
graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 3;
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 2;
graph.edge[4].src = 1;
graph.edge[4].dest = 4;
graph.edge[4].weight = 2;
graph.edge[5].src = 3;
graph.edge[5].dest = 2;
graph.edge[5].weight = 5;
graph.edge[6].src = 3;
graph.edge[6].dest = 1;
graph.edge[6].weight = 1;
graph.edge[7].src = 4;
graph.edge[7].dest = 3;
graph.edge[7].weight = -3;
int src = 0;
graph.BellmanFord(graph, src);
}
}
Brute-force Algorithm for Searching
public class BruteForceSearch {
public static int search(String text, String pattern) {
int n = text.length();
int m = pattern.length();
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (text.charAt(i + j) != pattern.charAt(j)) {
break;
}
}
if (j == m) {
return i; // Pattern found at index i
}
}
return -1; // Pattern not found
}
public static void main(String[] args) {
String text = "hello world";
String pattern = "world";
int result = search(text, pattern);
if (result == -1) {
System.out.println("Pattern not found");
} else {
System.out.println("Pattern found at index " + result);
}
}
}
Rabin-Karp String Matching Algorithm
class RabinKarp
{
public static int search(String text, String pattern)
{
char[] textArray = text.toCharArray();
char[] patternArray = pattern.toCharArray();
int n = text.length(), m = pattern.length(), prime = 101, pown = 1, textHash = 0, patternHash = 0, i, j;
if (m == 0 || m > n)
return -1;
for (i = 0; i < m - 1; i++)
pown = (pown << 1) % prime;
for (i = 0; i < m; i++)
{
patternHash = ((patternHash << 1) + patternArray[i]) % prime;
textHash = ((textHash << 1) + textArray[i]) % prime;
}
for (i = 0; i <= (n - m); i++)
{
if (textHash == patternHash)
{
for (j = 0; j < m; j++)
if (textArray[i + j] != patternArray[j])
break;
if (j == m)
return i;
}
if (i < n - m)
{
textHash = (((textHash - textArray[i] * pown) << 1) + textArray[i + m]) % prime;
if (textHash < 0)
textHash += prime;
}
}
return -1;
}
public static void main(String[] args)
{
String river = "Bro really said oh ethire the start position and end position duita jaga mention heichi. Let's add a random the here which we are to find.";
String drop = "the";
int index = search(river, drop);
if (index != -1)
System.out.println("Pattern found at index: " + (index+1));
else
System.out.println("Pattern not found.");
}
}
Symbol Table / Dictionary
import java.util.HashMap
class SymbolTable {
private HashMap table;
public SymbolTable() {
table = new HashMap<>();
}
public void put(String key, Integer value) {
table.put(key, value);
}
public Integer get(String key) {
return table.get(key);
}
public boolean contains(String key) {
return table.containsKey(key);
}
public void delete(String key) {
table.remove(key);
}
public static void main(String[] args) {
SymbolTable st = new SymbolTable();
st.put("a", 1);
st.put("b", 2);
System.out.println(st.get("a")); // 1
System.out.println(st.contains("b")); // true
st.delete("a");
System.out.println(st.contains("a")); // false
}
}
Hash Table
import java.util.LinkedList
class HashTable {
private class HashNode {
K key;
V value;
HashNode next;
public HashNode(K key, V value) {
this.key = key;
this.value = value;
}
}
private LinkedList>[] chainArray;
private int M = 11; // default number of chains
private int size;
public HashTable() {
chainArray = new LinkedList[M];
for (int i = 0; i < M; i++) {
chainArray[i] = new LinkedList>();
}
}
private int hash(K key) {
return Math.abs(key.hashCode() % M);
}
public void put(K key, V value) {
int index = hash(key);
for (HashNode node : chainArray[index]) {
if (node.key.equals(key)) {
node.value = value;
return;
}
}
chainArray[index].add(new HashNode(key, value));
size++;
}
public V get(K key) {
int index = hash(key);
for (HashNode node : chainArray[index]) {
if (node.key.equals(key)) {
return node.value;
}
}
return null;
}
public V remove(K key) {
int index = hash(key);
for (HashNode node : chainArray[index]) {
if (node.key.equals(key)) {
V value = node.value;
chainArray[index].remove(node);
size--;
return value;
}
}
return null;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size() == 0;
}
public static void main(String[] args) {
HashTable map = new HashTable<>();
map.put("this", 1);
map.put("coder", 2);
map.put("this", 4);
map.put("hi", 5);
System.out.println(map.size());
System.out.println(map.remove("this"));
System.out.println(map.remove("this"));
System.out.println(map.size());
System.out.println(map.isEmpty());
}
}
Anagrams
class Anyagram
{
static boolean areAnagram(String str1, String str2)
{
if (str1.length() != str2.length())
return false;
int count[] = new int[256]; //character range
for (int i = 0; i < str1.length(); i++)
{
count[str1.charAt(i)]++;
count[str2.charAt(i)]--;
}
for (int i = 0; i < 256; i++)
if (count[i] != 0)
return false;
return true;
}
public static void main(String[] args)
{
String str1 = "jaiphula";
String str2 = "phulajai";
if (areAnagram(str1, str2))
System.out.print("Are anagrams.");
else
System.out.print("Nope.");
}
}
Interval Scheduling
import java.util.*;
class Job implements Comparable {
int start, finish;
public Job(int start, int finish) {
this.start = start;
this.finish = finish;
}
public int compareTo(Job other) {
return this.finish - other.finish;
}
}
public class IntervalScheduling {
public static List intervalScheduling(List jobs) {
Collections.sort(jobs);
List result = new ArrayList<>();
int lastFinishTime = 0;
for (Job job : jobs) {
if (job.start >= lastFinishTime) {
result.add(job);
lastFinishTime = job.finish;
}
}
return result;
}
public static void main(String[] args) {
List jobs = new ArrayList<>();
jobs.add(new Job(1, 2));
jobs.add(new Job(3, 4));
jobs.add(new Job(0, 6));
jobs.add(new Job(5, 7));
jobs.add(new Job(8, 9));
jobs.add(new Job(5, 9));
List result = intervalScheduling(jobs);
System.out.println("Selected jobs:");
for (Job job : result) {
System.out.println("Job starts at: " + job.start + " and finishes at: " + job.finish);
}
}
}
Fractional Knapsack
import java.util.*
class FractionalKnapsack
{
public static void main(String[] args)
{
int val[] = { 60, 40, 90, 120 };
int weight[] = { 10, 40, 20, 30 };
int W = 50;
double ratio[][] = new double[val.length][2];
// 0th col = idx; 1st col ratio
for (int i = 0; i < val.length; i++)
{
ratio[i][0] = i;
ratio[i][1] = val[i] / (double) weight[i];
}
// ascending order
Arrays.sort(ratio, Comparator.comparingDouble(o -> o[1]));
int capacity = W;
int finalVal = 0;
for (int i = ratio.length - 1; i >= 0; i--)
{
int idx = (int) ratio[i][0];
if (capacity >= weight[idx]) // include full item
{
finalVal += val[idx];
capacity -= weight[idx];
}
else // include fractional item
{
finalVal += (ratio[i][1] * capacity);
capacity = 0;
break;
}
}
System.out.println("final value = " + finalVal);
}
}
Huffman Coding
import java.util.PriorityQueue;
import java.util.Comparator;
class HuffmanNode {
int data;
char c;
HuffmanNode left;
HuffmanNode right;
}
class MyComparator implements Comparator {
public int compare(HuffmanNode x, HuffmanNode y) {
return x.data - y.data;
}
}
public class HuffmanCoding {
public static void printCode(HuffmanNode root, String s) {
if (root.left == null && root.right == null && Character.isLetter(root.c)) {
System.out.println(root.c + ":" + s);
return;
}
printCode(root.left, s + "0");
printCode(root.right, s + "1");
}
public static void main(String[] args) {
int n = 6;
char[] charArray = {'a', 'b', 'c', 'd', 'e', 'f'};
int[] charfreq = {5, 9, 12, 13, 16, 45};
PriorityQueue q = new PriorityQueue(n, new MyComparator());
for (int i = 0; i < n; i++) {
HuffmanNode hn = new HuffmanNode();
hn.c = charArray[i];
hn.data = charfreq[i];
hn.left = null;
hn.right = null;
q.add(hn);
}
HuffmanNode root = null;
while (q.size() > 1) {
HuffmanNode x = q.poll();
HuffmanNode y = q.poll();
HuffmanNode f = new HuffmanNode();
f.data = x.data + y.data;
f.c = '-';
f.left = x;
f.right = y;
root = f;
q.add(f);
}
printCode(root, "");
}
}
Merge Sort
class MergeSort
{
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
int L[] = new int[n1];
int R[] = new int[n2];
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j]){
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void sort(int arr[], int l, int r)
{
if (l < r)
{
int m = (l + r) / 2;
sort(arr, l, m);
sort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
static void printArray(int arr[])
{
int size = arr.length;
System.out.print("{ ");
for (int i = 0; i < size-1; i++)
System.out.print(arr[i] + ", ");
System.out.print(arr[size-1] + " }");
System.out.println();
}
public static void main(String args[])
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
System.out.print("Given Array: ");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length - 1);
System.out.print("Sorted array: ");
printArray(arr);
}
}
Counting Inversions
class CountingInversion
{
static int getInvCount(int arr[], int n)
{
int inv_count = 0;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] > arr[j])
inv_count++;
return inv_count;
}
public static void main(String[] args)
{
int arr[] = new int[] {1, 20, 6, 4, 5};
System.out.println("Number of inversions are " + getInvCount(arr, arr.length));
}
}
Counting Inversion Using Merge Sort
public class CountInversions {
static int mergeAndCount(int[] arr, int l, int m, int r) {
int[] left = Arrays.copyOfRange(arr, l, m + 1);
int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);
int i = 0, j = 0, k = l, swaps = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j])
arr[k++] = left[i++];
else {
arr[k++] = right[j++];
swaps += (m + 1) - (l + i);
}
}
while (i < left.length)
arr[k++] = left[i++];
while (j < right.length)
arr[k++] = right[j++];
return swaps;
}
static int mergeSortAndCount(int[] arr, int l, int r) {
int count = 0;
if (l < r) {
int m = (l + r) / 2;
count += mergeSortAndCount(arr, l, m);
count += mergeSortAndCount(arr, m + 1, r);
count += mergeAndCount(arr, l, m, r);
}
return count;
}
public static void main(String[] args) {
int[] arr = {1, 20, 6, 4, 5};
System.out.println("Number of inversions are " + mergeSortAndCount(arr, 0, arr.length - 1));
}
}
Quick Sort
import java.util.Arrays;
class QuickSort
{
public static void main(String args[])
{
int arr[] = { 7, 6, 10, 5, 9, 2, 1, 15, 7 };
int n = arr.length;
QuickSort ob = new QuickSort();
ob.quickSort(arr, 0, n - 1);
System.out.print("Sorted array: ");
ob.printArray(arr, n);
}
int partition(int arr[], int low, int high)
{
int pivot = arr[low];
int k = high;
for (int i = high; i > low; i--)
if (arr[i] > pivot)
swap(arr, i, k--);
swap(arr, low, k);
return k;
}
public static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int idx = partition(arr, low, high);
quickSort(arr, low, idx - 1);
quickSort(arr, idx + 1, high);
}
}
void printArray(int arr[], int size)
{
int i;
System.out.print("{ ");
for (i = 0; i < size-1; i++)
System.out.print(arr[i] + ", ");
System.out.print(arr[size-1] + " }");
System.out.println();
}
}
Weighted Interval Scheduling
import java.util.Arrays;
import java.util.Comparator;
class Job {
int start, finish, weight;
Job(int start, int finish, int weight) {
this.start = start;
this.finish = finish;
this.weight = weight;
}
}
public class WeightedIntervalScheduling {
static int latestNonConflict(Job[] jobs, int i) {
for (int j = i - 1; j >= 0; j--) {
if (jobs[j].finish <= jobs[i].start)
return j;
}
return -1;
}
static int findMaxWeight(Job[] jobs, int n) {
Arrays.sort(jobs, new Comparator() {
public int compare(Job a, Job b) {
return a.finish - b.finish;
}
});
int[] dp = new int[n];
dp[0] = jobs[0].weight;
for (int i = 1; i < n; i++) {
int inclProf = jobs[i].weight;
int l = latestNonConflict(jobs, i);
if (l != -1)
inclProf += dp[l];
dp[i] = Math.max(inclProf, dp[i - 1]);
}
return dp[n - 1];
}
public static void main(String[] args) {
Job[] jobs = {new Job(1, 2, 50), new Job(3, 5, 20), new Job(6, 19, 100), new Job(2, 100, 200)};
System.out.println("Optimal weight is " + findMaxWeight(jobs, jobs.length));
}
}
Longest Common Subsequence
public class LCS {
int lcs(char[] X, char[] Y, int m, int n) {
int L[][] = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i - 1] == Y[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
}
}
return L[m][n];
}
public static void main(String[] args) {
LCS lcs = new LCS();
String s1 = "AGGTAB";
String s2 = "GXTXAYB";
char[] X = s1.toCharArray();
char[] Y = s2.toCharArray();
int m = X.length;
int n = Y.length;
System.out.println("Length of LCS is " + lcs.lcs(X, Y, m, n));
}
}
Matrix Chain Multiplication
import java.util.*;
class MatrixChainMultiplication
{
static int[][] m = new int[100][100];
static int matrixChain(int[] d, int i, int j)
{
if (i == j)
return 0;
if (m[i][j] != -1)
return m[i][j];
m[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++)
m[i][j] = Math.min(m[i][j], matrixChain(d, i, k) + matrixChain(d, k + 1, j) + d[i - 1] * d[k] * d[j]);
return m[i][j];
}
static int MatrixChainOrder(int[] d, int n) {
int i = 1, j = n - 1;
return matrixChain(d, i, j);
}
public static void main(String[] args)
{
int[] arr = { 2, 3, 4, 1, 5 }; //A2x3 x B3x4 x C4x1 x D1x5
int n = arr.length;
for (int[] row : m)
Arrays.fill(row, -1);
System.out.println("Minimum number of multiplications is " + MatrixChainOrder(arr, n));
}
}
Knapsack 0/1
public class Knapsack {
static int max(int a, int b) {
return (a > b) ? a : b;
}
static int knapSack(int W, int wt[], int val[], int n) {
int K[][] = new int[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
public static void main(String args[]) {
int val[] = new int[] { 60, 100, 120 };
int wt[] = new int[] { 10, 20, 30 };
int W = 50;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
0-1 Knapsack Top-Down Approach
import java.util.Arrays;
public class KnapsackTopDown {
static int[][] dp;
static int knapSackRec(int W, int wt[], int val[], int n) {
if (n == 0 || W == 0)
return 0;
if (dp[n][W] != -1)
return dp[n][W];
if (wt[n - 1] <= W)
return dp[n][W] = Math.max(val[n - 1] + knapSackRec(W - wt[n - 1], wt, val, n - 1), knapSackRec(W, wt, val, n - 1));
else
return dp[n][W] = knapSackRec(W, wt, val, n - 1);
}
static int knapSack(int W, int wt[], int val[], int n) {
dp = new int[n + 1][W + 1];
for (int[] row : dp)
Arrays.fill(row, -1);
return knapSackRec(W, wt, val, n);
}
public static void main(String args[]) {
int val[] = new int[] { 60, 100, 120 };
int wt[] = new int[] { 10, 20, 30 };
int W = 50;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
Subset Sum
class sebsetAchhi
{
public static void main(String args[])
{
int set[] = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = set.length;
if (isSubsetSum(set, n, sum) == true)
System.out.println("Found a subset"
+ " with given sum");
else
System.out.println("No subset with"
+ " given sum");
}
static boolean isSubsetSum(int set[], int n, int sum)
{
if (sum == 0)
return true;
if (n == 0)
return false;
if (set[n - 1] > sum)
return isSubsetSum(set, n - 1, sum);
return isSubsetSum(set, n - 1, sum)
|| isSubsetSum(set, n - 1, sum - set[n - 1]);
}
}