Optimized Programs (17CSL47)

=> Program 6(a) 0/1 Knapsack Dynamic Programming :

package com.sunchit.company;
import java.util.Scanner;

public class Main {

static int v[][] = new int[20][20];

public static int max1(int a, int b) {

return (a > b) ? a : b;
}

public static void main(String[] args) {

int p[] = new int[20];

int w[] = new int[20];
int i, j, n, max;
Scanner sn = new Scanner(System.in);

System.out.println("Enter no. of items");

n = sn.nextInt();
for (i = 1; i <= n; i++) {
System.out.println("Enter weight & profit of item:" + i);
w[i] = sn.nextInt();

p[i] = sn.nextInt();
}
 System.out.println("Enter Capacity");
max = sn.nextInt();
for (i = 0; i <= n; i++)

v[i][0] = 0;
for (j = 0; j <= max; j++)
v[0][j] = 0;
for (i = 1; i <= n; i++) {

for (j = 1; j <= max; j++) {

if (w[i] > j)
v[i][j] = v[i - 1][j];
else

v[i][j] = max1(v[i - 1][j], v[i - 1][j - w[i]] + p[i]);

}
}
System.out.println("Profit:" + v[n][max]);
System.out.println("items Selected:");

j = max;
for (i = n; i >= 1; i--)
if (v[i][j] != v[i - 1][j]) {
System.out.println("\tItem:" + i);
j = j - w[i];
}
}
}
=> Program 6(b) Knapsack Greedy Method :

package com.sunchit.company;
import java.util.*;

public class Main {

public static void knapsack(int n,int []item, float[] weight, float[] profit, float max) {
float tp = 0, u;
int i;
u = max;
float[] x = new float[20];

for (i = 0; i < n; i++)

x[i] = (float) 0.0;
for (i = 0; i < n; i++) {
if (weight[i] > u) {

break;
} else {
x[i] = (float) 1.0;
tp = tp + profit[i];

u = (int) u - weight[i];
}
}
if (i < n)

x[i] = u / weight[i];
 tp = tp + (x[i] * profit[i]);
System.out.println("Resultant Vector");
for (i = 0; i < n; i++)

System.out.println("Item:\t"+item[i]+"\tratio:\t"+x[i]);
System.out.println("Profit Max:" + tp);
}

public static void main(String[] args) {

float weight[] = new float[20];
float profit[] = new float[20];
float capacity;

int num, i, j;
float ratio[] = new float[20], temp;
int item[] = new int[10];
Scanner sn = new Scanner(System.in);
System.out.println("\nEnter the no. of objects:- ");

num = sn.nextInt();
for (i = 0; i < num; i++)
item[i] = i + 1;
System.out.println("\nEnter the weights and profits of each object:- ");
for (i = 0; i < num; i++) {
weight[i] = sn.nextFloat();
profit[i] = sn.nextFloat();
}

System.out.println("\nEnter the capacity of knapsack:- ");

capacity = sn.nextFloat();
for (i = 0; i < num; i++) {
 ratio[i] = profit[i] / weight[i];
}
for (i = 0; i < num; i++) {

for (j = i + 1; j < num; j++) {

if (ratio[i] < ratio[j]) {
temp = ratio[j];
ratio[j] = ratio[i];

ratio[i] = temp;

temp = weight[j];
weight[j] = weight[i];

weight[i] = temp;

temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;

temp = item[j];
item[j] = item[i];
item[i] = (int) temp;
}
}
}
knapsack(num,item, weight, profit, capacity);

}
}
=> Program 7 Dijkstra's Single Source Shortest Path:

package com.sunchit.company;
import java.util.*;

public class Main {

public int distance[] = new int[10];
public int cost[][] = new int[10][10];

public void calc(int n, int s) {

int flag[] = new int[n + 1];

int i, minpos = 1, k, c, minimum;
for (i = 1; i <= n; i++) {
flag[i] = 0;

this.distance[i] = this.cost[s][i];
}
c = 2;
while (c <= n) {

minimum = 999;
for (k = 1; k <= n; k++) {
if (this.distance[k] < minimum && flag[k] != 1) {
minimum = this.distance[k];
 minpos = k;
}
}

flag[minpos] = 1;
c++;
for (k = 1; k <= n; k++) {
if (this.distance[minpos] + this.cost[minpos][k] < this.distance[k] && flag[k] != 1)

this.distance[k] = this.distance[minpos] + this.cost[minpos][k];

}
}
}

public static void main(String args[]) {

int nodes, source, i, j;
Scanner in = new Scanner(System.in);
System.out.println("Enter the Number of Nodes \n");

nodes = in.nextInt();
Main d = new Main();
System.out.println("Enter the Cost Matrix Weights: \n");
for (i = 1; i <= nodes; i++)
for (j = 1; j <= nodes; j++) {
d.cost[i][j] = in.nextInt();
if (d.cost[i][j] == 0)
d.cost[i][j] = 999;

}
System.out.println("Enter the Source Vertex :\n");
source = in.nextInt();
 d.calc(nodes, source);
System.out.println("The Shortest Path from Source " + source + " to all other vertices are :
\n");

for (i = 1; i <= nodes; i++)

if (i != source)
System.out.println("source :" + source + "\t destination :" + i + "\t MinCost is :" +
d.distance[i] + "\t");

}
}

=> Program 8 Kruskal's MST Union Find Method:

package com.sunchit.company;
import java.util.Scanner;

public class Main {

int[] parent = new int[10];

int find(int m) {
int p = m;
while (parent[p] != 0)

p = parent[p];
return p;
}

void union(int i, int j) {

if (i < j)
parent[i] = j;
else
parent[j] = i;

public void krkl(int a[][], int n) {

int u = 0, v = 0, k = 0, i, j, minimum;

int sum = 0;
while (k < n - 1) {
minimum = 999;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)

if (minimum > a[i][j] && i != j) {

minimum = a[i][j];
u = i;
v = j;
}
i = find(u);
j = find(v);
if (i != j) {

union(i, j);
sum = sum + a[u][v];
System.out.println("(" + u + "," + v + ")" + "=" + a[u][v]);
 k++;
}
a[u][v] = a[v][u] = 999;

}
System.out.println("Minimum Cost: "+sum);
}

public static void main(String[] args) {

int[][] a = new int[10][10];
int i, j;
System.out.println("Enter no.of vertices");

Scanner sn = new Scanner(System.in);

int n = sn.nextInt();
System.out.println("Enter weighted matrix:");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)

a[i][j] = sn.nextInt();
Main k = new Main();
k.krkl(a, n);
}
}

=> Program 9 Prim's MST Greedy Method:

package com.sunchit.company;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
int w[][] = new int[10][10];
int n, i, j, s, k = 0;

int min;
int sum = 0;
int u = 0, v = 0;
int flag = 0;
int sol[] = new int[10];

System.out.println("Enter the number of vertices");

Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (i = 1; i <= n; i++)

sol[i] = 0;
System.out.println("Enter the weighted graph");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)

w[i][j] = sc.nextInt();
System.out.println("Enter the source vertex");
s = sc.nextInt();
sol[s] = 1;

k = 1;
 while (k <= n - 1) {
min = 99;
for (i = 1; i <= n; i++) {

for (j = 1; j <= n; j++) {

if (sol[i] == 1 && sol[j] == 0) {
if (i != j && min > w[i][j]) {
min = w[i][j];

u = i;
v = j;
}
}

}
}
sol[v] = 1;
sum = sum + min;
k++;

System.out.println(u + "->" + v + "=" + min);

}
for (i = 1; i <= n; i++)
if (sol[i] == 0)
flag = 1;
if (flag == 1)
System.out.println("No spanning tree");
else

System.out.println("The cost of minimum spanning tree is" + sum);

sc.close();
}
}

=> Program 10(a) Floyd's All Pairs Shortest Path:

package com.sunchit.company;
import java.util.*;

public class Main {

void flyd(int[][] w, int n) {

int i, j, k;
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

w[i][j] = Math.min(w[i][j], w[i][k] + w[k][j]);
}

public static void main(String[] args) {

int a[][] = new int[10][10];
int n, i, j;
System.out.println("enter the number of vertices");
Scanner sc = new Scanner(System.in);

n = sc.nextInt();
 System.out.println("Enter the weighted matrix");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)

a[i][j] = sc.nextInt();
Main f = new Main();
f.flyd(a, n);
System.out.println("The shortest path matrix is");

for (i = 1; i <= n; i++) {

for (j = 1; j <= n; j++) {
System.out.print(a[i][j] + " ");
}

System.out.println();
}
sc.close();
}
}

=> Program 10(b) Travelling Sale's Problem Dynamic :

package com.sunchit.company;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sn = new Scanner(System.in);

int c[][] = new int[10][10];

int tour[] = new int[10];
int n, i, j, cost;
System.out.println("Enter the no. of cities");

n = sn.nextInt();
if (n == 1) {
System.out.println("No Paths Possible");
System.exit(0);

}
System.out.println("Enter the cost adjacency matrix");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
c[i][j] = sn.nextInt();

for (i = 1; i <= n; i++)

tour[i] = i;
cost = tspdp(c, tour, 1, n);
System.out.println("Optimal Tour:");
for (i = 1; i <= n; i++)
System.out.print(tour[i] + "-->");
System.out.println("1");

System.out.println("Minimum Cost: " + cost);

}
 public static int tspdp(int c[][], int tour[], int start, int n) {
int temp[] = new int[10];
int mintour[] = new int[10];

int minimum = 999, i, k, j, ccost;

if (start == n - 1) {
return (c[tour[n - 1]][tour[n]] + c[tour[n]][1]);
}

for (i = start + 1; i <= n; i++) {

for (k = 1; k <= n; k++)
temp[k] = tour[k];
temp[start + 1] = tour[i];

temp[i] = tour[start + 1];

if ((c[tour[start]][tour[i]] + (ccost = tspdp(c, temp, start + 1, n))) < minimum) {
minimum = c[tour[start]][tour[i]] + ccost;
for (j = 1; j <= n; j++)
mintour[j] = temp[j];

}
}
for (k = 1; k <= n; k++)
tour[k] = mintour[k];
return minimum;
}

}
=> Program 11 Subset Problem :

package com.sunchit.company;
import java.util.Scanner;

public class Main {

public void subset(int num, int n, int x[]) {

int i;
for (i = 1; i <= n; i++)
x[i] = 0;

for (i = n; num != 0; i--) {

x[i] = num % 2;
num = num / 2;
}

public static void main(String[] args) {

Scanner sn = new Scanner(System.in);

int[] a = new int[10];

int[] x = new int[10];
int n, i,j, d, sum;
int present = 0;

System.out.println("Enter no. of elements in set");

n = sn.nextInt();
System.out.println("Enter the elements of set");
for (i = 1; i <= n; i++)

a[i] = sn.nextInt();
System.out.println("Enter the desired sum");
d = sn.nextInt();
if (d > 0) {

for (i = 1; i <= Math.pow(2, n) - 1; i++) {

Main s = new Main();
s.subset(i, n, x);
sum = 0;

for (j = 1; j <= n; j++)

if (x[j] ==1)
sum = sum + a[j];
if (d == sum) {
present = 1;

System.out.print("Subset:{ ");
for (j = 1; j <= n; j++)
if (x[j] ==1)
System.out.print(a[j] + ",");
System.out.print("} =" + d);
System.out.println();
}
}

}
if (present == 0)
System.out.println("No such Solution");
 }
}

=> Program 12 Hamiltonian Cycles Backtracking:

package com.sunchit.example
import java.util.Scanner;

public class Main

{
static int x[] = new int[10];
public static void main(String[] args)
{

Scanner sc = new Scanner(System.in);

int i,j,x1, x2, edges, n;
int g[][] = new int[10][10];
System.out.print("Enter No. of Vertices: ");

n = sc.nextInt();
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)

{
g[i][j] = 0;
 x[i]=0;
}
}

System.out.print("Enter No. of Edges: ");

edges = sc.nextInt();
for(i=1;i<=edges;i++)

{
System.out.println("Enter the Edge"+i+": ");
x1 = sc.nextInt();
x2 = sc.nextInt();

g[x1][x2] = 1;
g[x2][x1] = 1;
}
x[1] = 1;
System.out.println("\nHamiltonian Cycle");

hcycle(g,n,2);
}

public static void nextvalue(int g[][],int n,int k)

{
int j;
while(true)
{

x[k] = (x[k] + 1) % (n+1);

if(x[k] == 0)
return;
 if(g[x[k-1]][x[k]] == 1)
{
for(j=1;j<=k-1;j++)

{
if(x[j] == x[k] )
break;
}

if(j == k)
{
if((k<n) || ((k==n) && (g[x[n]][x[1]] == 1)))
return;

}
}
}
}

public static void hcycle(int g[][],int n, int k)

{
int i;
while(true)
{
nextvalue(g,n,k);
if(x[k]== 0)
return;

if(k==n)
{
for(i=1;i<=n;i++)
 System.out.print(x[i]+"-->");
System.out.println(x[1]+"\n");
}

else
hcycle(g,n,k+1);
}
}

1MV17CS127

Sunchit Lakhanpal