merge sort

import java.util.Scanner;
public class Mergesort {
private static void merge(int[] array, int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;

int[] leftArray = new int[n1];

int[] rightArray = new int[n2];

for (int i = 0; i < n1; ++i) {

leftArray[i] = array[left + i];
}
for (int j = 0; j < n2; ++j) {
rightArray[j] = array[middle + 1 + j];
}

int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
array[k] = leftArray[i];
i++;
} else {
array[k] = rightArray[j];
j++;
}
k++;
}

while (i < n1) {

array[k] = leftArray[i];
i++;
k++;
}

while (j < n2) {

array[k] = rightArray[j];
j++;
k++;
}
}
private static void mergeSort(int[] array, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;

mergeSort(array, left, middle);

mergeSort(array, middle + 1, right);

merge(array, left, middle, right);

}
}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.println("Enter the array size");

int size = scanner.nextInt();

int[] array = new int[size];

System.out.println("Enter the elements of the array:");

for (int i = 0; i < size; i++) {
array[i] = scanner.nextInt();
 }

System.out.println("Array before sorting:");

for (int num : array) {
System.out.println(num);
}

long startTime = System.nanoTime();

mergeSort(array, 0, array.length - 1);
long endTime = System.nanoTime();
long elapsedTime = endTime - startTime;

System.out.println("Sorted array is:");

for (int num : array) {
System.out.println(num);
} }
}

knapsank

import java.util.Arrays;
import java.util.Scanner;

public class Knapsack {

// Item class to store value and weight of each item

static class Item implements Comparable<Item> {
int value, weight;

// Constructor
public Item(int value, int weight) {
this.value = value;
this.weight = weight;
}

// Method to compare items based on value-to-weight ratio

@Override
public int compareTo(Item other) {
double thisRatio = (double) this.value / this.weight;
double otherRatio = (double) other.value / other.weight;
return Double.compare(otherRatio, thisRatio);
}
}

// Method to calculate the maximum profit using Greedy approach

public static int getMaxProfit(Item[] items, int capacity) {
Arrays.sort(items);

int totalProfit = 0;
int remainingCapacity = capacity;

for (Item item : items) {

if (item.weight <= remainingCapacity) {
totalProfit += item.value;
remainingCapacity -= item.weight;
} else {
totalProfit += item.value * ((double) remainingCapacity /
item.weight);
break;
}
}

return totalProfit;
 }

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.print("Enter the number of items:");

int numItems = scanner.nextInt();

Item[] items = new Item[numItems];

System.out.println("Enter the values and weights of the items:");

for (int i = 0; i < numItems; i++) {
int value = scanner.nextInt();
int weight = scanner.nextInt();
items[i] = new Item(value, weight);
}

System.out.print("Enter the knapsack capacity:");

int capacity = scanner.nextInt();

int maxProfit = getMaxProfit(items, capacity);

System.out.println("Maximum Profit: " + maxProfit);

}
}

Knapsack Problem using Brute Force

import java.util.Scanner;

public class test{

public static int knapsack(int[] values, int[] weights, int capacity, int n)
{
if (n == 0 || capacity == 0) {
return 0;
}

if (weights[n - 1] > capacity) {

return knapsack(values, weights, capacity, n - 1);
} else {
int include = values[n - 1] + knapsack(values, weights, capacity -
weights[n - 1], n - 1);
int exclude = knapsack(values, weights, capacity, n - 1);
return Math.max(include, exclude);
}
}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

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

int numItems = scanner.nextInt();

int[] values = new int[numItems];

int[] weights = new int[numItems];

System.out.println("Enter the values of the items:");

for (int i = 0; i < numItems; i++) {
values[i] = scanner.nextInt();
}

System.out.println("Enter the weights of the items:");

 for (int i = 0; i < numItems; i++) {
weights[i] = scanner.nextInt();
}

System.out.println("Enter the knapsack capacity:");

int capacity = scanner.nextInt();

int maxProfit = knapsack(values, weights, capacity, numItems);

System.out.println("Maximum Profit: " + maxProfit);

}
}

knapsack proplem using dynamic programming

import java.util.Scanner;

public class KnapsackDP {

public static int knapsack(int[] values, int[] weights, int capacity) {

int n = values.length;
int[][] dp = new int[n + 1][capacity + 1];

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

for (int w = 1; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(dp[i - 1][w], values[i - 1] + dp[i - 1]
[w - weights[i - 1]]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}

return dp[n][capacity];
}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

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

int numItems = scanner.nextInt();

int[] values = new int[numItems];

int[] weights = new int[numItems];

System.out.println("Enter the values of the items:");

for (int i = 0; i < numItems; i++) {
values[i] = scanner.nextInt();
}

System.out.println("Enter the weights of the items:");

for (int i = 0; i < numItems; i++) {
weights[i] = scanner.nextInt();
}

System.out.println("Enter the knapsack capacity:");

int capacity = scanner.nextInt();

int maxProfit = knapsack(values, weights, capacity);

 System.out.println("Maximum Profit: " + maxProfit);
}
}

prims alg

import java.util.Scanner;

public class Main{

public static int findMinVertex(int[] key, boolean[] mstSet, int vertices) {

int minKey = Integer.MAX_VALUE;
int minIndex = -1;

for (int v = 0; v < vertices; v++) {

if (!mstSet[v] && key[v] < minKey) {
minKey = key[v];
minIndex = v;
}
}
return minIndex;
}

public static void primMST(int[][] graph, int vertices) {

int[] parent = new int[vertices];
int[] key = new int[vertices];
boolean[] mstSet = new boolean[vertices];

for (int i = 0; i < vertices; i++) {

key[i] = Integer.MAX_VALUE;
mstSet[i] = false;
}

key[0] = 0;
parent[0] = -1;

for (int count = 0; count < vertices - 1; count++) {

int u = findMinVertex(key, mstSet, vertices);
mstSet[u] = true;

for (int v = 0; v < vertices; v++) {

if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}

int totalCost = 0;
for (int i = 1; i < vertices; i++) {
totalCost += graph[i][parent[i]];
}

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

System.out.println("Edges in the minimum spanning tree:");
for (int i = 1; i < vertices; i++) {
System.out.println((parent[i] + 1) + " - " + (i + 1));
}
}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);
 System.out.println("Enter the number of vertices:");
int vertices = scanner.nextInt();

int[][] graph = new int[vertices][vertices];

System.out.println("Enter the cost matrix:");

for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
graph[i][j] = scanner.nextInt();
}
}

primMST(graph, vertices);
}
}