Skip to content

Commit 535230a

Browse files
VineettttVineetttt
authored
Add Greedy Algorithms (fixes TheAlgorithms#4493) (TheAlgorithms#4504)
1 parent 329cc3b commit 535230a

File tree

8 files changed

+336
-0
lines changed

8 files changed

+336
-0
lines changed

‎src/main/java/com/thealgorithms/greedyalgorithms/ActivitySelection.java

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package com.thealgorithms.greedyalgorithms;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.Comparator;
6+
7+
// Problem Link: https://en.wikipedia.org/wiki/Activity_selection_problem
8+
9+
public class ActivitySelection {
10+
// Function to perform activity selection
11+
public static ArrayList<Integer> activitySelection(int startTimes[], int endTimes[]) {
12+
int n = startTimes.length;
13+
int activities[][] = new int[n][3];
14+
15+
// Create a 2D array to store activities and their start/end times.
16+
// Each row: [activity index, start time, end time]
17+
18+
for (int i = 0; i < n; i++) {
19+
activities[i][0] = i; // Assign activity index
20+
activities[i][1] = startTimes[i]; // Assign start time
21+
activities[i][2] = endTimes[i]; // Assign end time
22+
}
23+
24+
// Sort activities by their end times in ascending order.
25+
Arrays.sort(activities, Comparator.comparingDouble(activity -> activity[2]));
26+
int lastEndTime;
27+
ArrayList<Integer> selectedActivities = new ArrayList<>();
28+
selectedActivities.add(activities[0][0]);
29+
lastEndTime = activities[0][2];
30+
31+
// Iterate through sorted activities to select compatible ones.
32+
for (int i = 1; i < n; i++) {
33+
if (activities[i][1] >= lastEndTime) {
34+
selectedActivities.add(activities[i][0]);
35+
lastEndTime = activities[i][2];
36+
}
37+
}
38+
return selectedActivities;
39+
}
40+
}

‎src/main/java/com/thealgorithms/greedyalgorithms/CoinChange.java

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package com.thealgorithms.greedyalgorithms;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.Comparator;
6+
7+
// Problem Link : https://en.wikipedia.org/wiki/Change-making_problem
8+
9+
public class CoinChange {
10+
// Function to solve the coin change problem
11+
public static ArrayList<Integer> coinChangeProblem(int amount) {
12+
// Define an array of coin denominations in descending order
13+
Integer coins[] = {1, 2, 5, 10, 20, 50, 100, 500, 2000};
14+
15+
// Sort the coin denominations in descending order
16+
Arrays.sort(coins, Comparator.reverseOrder());
17+
18+
int count = 0; // Variable to keep track of the total number of coins used
19+
ArrayList<Integer> ans = new ArrayList<>(); // List to store selected coins
20+
21+
// Iterate through the coin denominations
22+
for (int i = 0; i < coins.length; i++) {
23+
// Check if the current coin denomination can be used to reduce the remaining amount
24+
if (coins[i] <= amount) {
25+
// Repeatedly subtract the coin denomination from the remaining amount
26+
while (coins[i] <= amount) {
27+
count++; // Increment the count of coins used
28+
ans.add(coins[i]); // Add the coin to the list of selected coins
29+
amount -= coins[i]; // Update the remaining amount
30+
}
31+
}
32+
}
33+
return ans;
34+
}
35+
}

‎src/main/java/com/thealgorithms/greedyalgorithms/FractionalKnapsack.java

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.thealgorithms.greedyalgorithms;
2+
3+
import java.util.Arrays;
4+
import java.util.Comparator;
5+
6+
// Problem Link: https://en.wikipedia.org/wiki/Continuous_knapsack_problem
7+
8+
public class FractionalKnapsack {
9+
// Function to perform fractional knapsack
10+
public static int fractionalKnapsack(int weight[], int value[], int capacity) {
11+
// Create a 2D array to store item indices and their value-to-weight ratios.
12+
double ratio[][] = new double[weight.length][2];
13+
14+
// Populate the ratio array with item indices and their value-to-weight ratios.
15+
for (int i = 0; i < weight.length; i++) {
16+
ratio[i][0] = i; // Assign item index.
17+
ratio[i][1] = value[i] / (double) weight[i]; // Calculate and assign value-to-weight ratio.
18+
}
19+
20+
// Sort items by their value-to-weight ratios in descending order.
21+
Arrays.sort(ratio, Comparator.comparingDouble(o -> o[1]));
22+
23+
int finalValue = 0; // Variable to store the final knapsack value.
24+
double current = capacity; // Variable to track the remaining capacity of the knapsack.
25+
26+
// Iterate through the sorted items to select items for the knapsack.
27+
for (int i = ratio.length - 1; i >= 0; i--) {
28+
int index = (int) ratio[i][0]; // Get the item index.
29+
if (current >= weight[index]) {
30+
// If the entire item can fit in the knapsack, add its value.
31+
finalValue += value[index];
32+
current -= weight[index];
33+
} else {
34+
// If only a fraction of the item can fit, add a proportionate value.
35+
finalValue += ratio[i][1] * current;
36+
break; // Stop adding items to the knapsack since it's full.
37+
}
38+
}
39+
return finalValue;
40+
}
41+
}

‎src/main/java/com/thealgorithms/greedyalgorithms/JobSequencing.java

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package com.thealgorithms.greedyalgorithms;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.Collections;
6+
7+
// Problem Link: https://en.wikipedia.org/wiki/Job-shop_scheduling
8+
9+
public class JobSequencing {
10+
11+
// Define a Job class that implements Comparable for sorting by profit in descending order
12+
static class Job implements Comparable<Job> {
13+
char id;
14+
int deadline;
15+
int profit;
16+
17+
// Compare jobs by profit in descending order
18+
@Override
19+
public int compareTo(Job otherJob) {
20+
return otherJob.profit - this.profit;
21+
}
22+
23+
public Job(char id, int deadline, int profit) {
24+
this.id = id;
25+
this.deadline = deadline;
26+
this.profit = profit;
27+
}
28+
}
29+
30+
// Function to print the job sequence
31+
public static String findJobSequence(ArrayList<Job> jobs, int size) {
32+
Boolean[] slots = new Boolean[size];
33+
Arrays.fill(slots, false);
34+
35+
int result[] = new int[size];
36+
37+
// Iterate through jobs to find the optimal job sequence
38+
for (int i = 0; i < size; i++) {
39+
for (int j = jobs.get(i).deadline - 1; j >= 0; j--) {
40+
if (!slots[j]) {
41+
result[j] = i;
42+
slots[j] = true;
43+
break;
44+
}
45+
}
46+
}
47+
48+
// Create a StringBuilder to build the job sequence string
49+
StringBuilder jobSequenceBuilder = new StringBuilder();
50+
jobSequenceBuilder.append("Job Sequence: ");
51+
for (int i = 0; i < jobs.size(); i++) {
52+
if (slots[i]) {
53+
jobSequenceBuilder.append(jobs.get(result[i]).id).append(" -> ");
54+
}
55+
}
56+
57+
// Remove the trailing " -> " from the job sequence
58+
if (jobSequenceBuilder.length() >= 4) {
59+
jobSequenceBuilder.setLength(jobSequenceBuilder.length() - 4);
60+
}
61+
62+
// Return the job sequence as a string
63+
return jobSequenceBuilder.toString();
64+
}
65+
}

‎src/test/java/com/thealgorithms/greedyalgorithms/ActivitySelectionTest.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.thealgorithms.greedyalgorithms;
2+
3+
import static org.junit.jupiter.api.Assertions.*;
4+
5+
import java.util.ArrayList;
6+
import java.util.Arrays;
7+
import org.junit.jupiter.api.Test;
8+
9+
public class ActivitySelectionTest {
10+
@Test
11+
public void testActivitySelection() {
12+
int start[] = {1, 3, 0, 5, 8, 5};
13+
int end[] = {2, 4, 6, 7, 9, 9};
14+
15+
ArrayList<Integer> result = ActivitySelection.activitySelection(start, end);
16+
ArrayList<Integer> expected = new ArrayList<>(Arrays.asList(0, 1, 3, 4));
17+
18+
assertEquals(expected, result);
19+
}
20+
21+
@Test
22+
public void testSingleActivity() {
23+
int start[] = {1};
24+
int end[] = {2};
25+
26+
ArrayList<Integer> result = ActivitySelection.activitySelection(start, end);
27+
ArrayList<Integer> expected = new ArrayList<>(Arrays.asList(0));
28+
29+
assertEquals(expected, result);
30+
}
31+
32+
@Test
33+
public void testNoOverlap() {
34+
int start[] = {1, 2, 3};
35+
int end[] = {2, 3, 4};
36+
37+
ArrayList<Integer> result = ActivitySelection.activitySelection(start, end);
38+
ArrayList<Integer> expected = new ArrayList<>(Arrays.asList(0, 1, 2));
39+
40+
assertEquals(expected, result);
41+
}
42+
}

‎src/test/java/com/thealgorithms/greedyalgorithms/CoinChangeTest.java

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package com.thealgorithms.greedyalgorithms;
2+
3+
import static org.junit.jupiter.api.Assertions.assertEquals;
4+
5+
import java.util.ArrayList;
6+
import java.util.Arrays;
7+
import org.junit.jupiter.api.Test;
8+
9+
public class CoinChangeTest {
10+
@Test
11+
public void testCoinChangeProblemWithValidAmount() {
12+
ArrayList<Integer> expected = new ArrayList<>(Arrays.asList(500, 50, 20, 20, 1));
13+
ArrayList<Integer> coins = CoinChange.coinChangeProblem(591);
14+
assertEquals(expected, coins);
15+
}
16+
17+
@Test
18+
public void testCoinChangeProblemWithLargeAmount() {
19+
ArrayList<Integer> expected = new ArrayList<>(Arrays.asList(2000));
20+
ArrayList<Integer> coins = CoinChange.coinChangeProblem(2000);
21+
assertEquals(expected, coins);
22+
}
23+
24+
@Test
25+
public void testCoinChangeProblemWithPartialCoins2() {
26+
ArrayList<Integer> expected = new ArrayList<>(Arrays.asList(500, 50, 20));
27+
ArrayList<Integer> coins = CoinChange.coinChangeProblem(570);
28+
assertEquals(expected, coins);
29+
}
30+
31+
@Test
32+
public void testCoinChangeProblemWithSmallAmount() {
33+
ArrayList<Integer> expected = new ArrayList<>(Arrays.asList(2, 1));
34+
ArrayList<Integer> coins = CoinChange.coinChangeProblem(3);
35+
assertEquals(expected, coins);
36+
}
37+
38+
@Test
39+
public void testCoinChangeProblemWithLargeAmountAndMultipleDenominations() {
40+
ArrayList<Integer> expected = new ArrayList<>(Arrays.asList(2000, 2000, 2000, 2000, 500, 500, 500, 100, 100, 100, 100, 50, 20, 20, 5, 2, 2));
41+
ArrayList<Integer> coins = CoinChange.coinChangeProblem(9999);
42+
assertEquals(expected, coins);
43+
}
44+
45+
@Test
46+
public void testCoinChangeProblemWithAllDenominations() {
47+
ArrayList<Integer> expected = new ArrayList<>(Arrays.asList(2000, 500, 100, 100, 100, 50, 20, 10, 5, 2, 1));
48+
ArrayList<Integer> coins = CoinChange.coinChangeProblem(2888);
49+
assertEquals(expected, coins);
50+
}
51+
52+
@Test
53+
public void testCoinChangeProblemWithZeroAmount() {
54+
ArrayList<Integer> expected = new ArrayList<>();
55+
ArrayList<Integer> coins = CoinChange.coinChangeProblem(0);
56+
assertEquals(expected, coins);
57+
}
58+
}

‎src/test/java/com/thealgorithms/greedyalgorithms/FractionalKnapsackTest.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.thealgorithms.greedyalgorithms;
2+
3+
import static org.junit.jupiter.api.Assertions.*;
4+
5+
import org.junit.jupiter.api.Test;
6+
7+
public class FractionalKnapsackTest {
8+
9+
@Test
10+
public void testFractionalKnapsackWithExampleCase() {
11+
int weight[] = {10, 20, 30};
12+
int value[] = {60, 100, 120};
13+
int capacity = 50;
14+
assertEquals(240, FractionalKnapsack.fractionalKnapsack(weight, value, capacity));
15+
}
16+
17+
@Test
18+
public void testFractionalKnapsackWithZeroCapacity() {
19+
int weight[] = {10, 20, 30};
20+
int value[] = {60, 100, 120};
21+
int capacity = 0;
22+
assertEquals(0, FractionalKnapsack.fractionalKnapsack(weight, value, capacity));
23+
}
24+
25+
@Test
26+
public void testFractionalKnapsackWithEmptyItems() {
27+
int weight[] = {};
28+
int value[] = {};
29+
int capacity = 50;
30+
assertEquals(0, FractionalKnapsack.fractionalKnapsack(weight, value, capacity));
31+
}
32+
}

‎src/test/java/com/thealgorithms/greedyalgorithms/JobSequencingTest.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package com.thealgorithms.greedyalgorithms;
2+
3+
import static org.junit.jupiter.api.Assertions.*;
4+
5+
import java.util.ArrayList;
6+
import java.util.Collections;
7+
import org.junit.jupiter.api.Test;
8+
9+
public class JobSequencingTest {
10+
@Test
11+
public void testJobSequencingWithExampleCase() {
12+
ArrayList<JobSequencing.Job> jobs = new ArrayList<>();
13+
jobs.add(new JobSequencing.Job('a', 2, 100));
14+
jobs.add(new JobSequencing.Job('b', 1, 19));
15+
jobs.add(new JobSequencing.Job('c', 2, 27));
16+
jobs.add(new JobSequencing.Job('d', 1, 25));
17+
jobs.add(new JobSequencing.Job('e', 3, 15));
18+
Collections.sort(jobs);
19+
String jobSequence = JobSequencing.findJobSequence(jobs, jobs.size());
20+
21+
assertEquals("Job Sequence: c -> a -> e", jobSequence);
22+
}
23+
}

0 commit comments

Comments
 (0)