Skip to content

Add greedy algorithm for minimum chocolate cutting cost #6247

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
wants to merge 2 commits into from
Closed

Add greedy algorithm for minimum chocolate cutting cost #6247

Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
21a0060
greedy solution for minimum chocolate cutting cost
aanya-srivastava May 25, 2025
50f97e2
greedy solution for minimum chocolate cutting cost
aanya-srivastava May 25, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
64 changes: 64 additions & 0 deletions src/main/java/com/thealgorithms/greedyalgorithms/Chocola.java
View file
Open in desktop
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Could you please add a test file and resolve the issues causing the pipelines to fail?

Original file line number Diff line number Diff line change
@@ -0,0 +1,64 @@
package com.thealgorithms.greedyalgorithms;

import java.util.Arrays;
import java.util.Collections;

/**
* Greedy approach to minimize the cost of cutting a chocolate bar into 1x1 pieces.
*/

public class Chocola {

/**
* Calculates the minimum cost of cutting the chocolate bar.
*
* @param costVer Cost of vertical cuts (size m-1)
* @param costHor Cost of horizontal cuts (size n-1)
* @return Minimum total cost
*/
public static int minCostOfCuttingChocolate(Integer[] costVer, Integer[] costHor) {
Arrays.sort(costVer, Collections.reverseOrder());
Arrays.sort(costHor, Collections.reverseOrder());

int h = 0, v = 0;
int hp = 1, vp = 1;

int cost = 0;

while (h < costHor.length && v < costVer.length) {
if (costHor[h] >= costVer[v]) {
cost += costHor[h] * vp;
h++;
hp++;
} else {
cost += costVer[v] * hp;
v++;
vp++;
}
}

while (h < costHor.length) {
cost += costHor[h] * vp;
h++;
hp++;
}

while (v < costVer.length) {
cost += costVer[v] * hp;
v++;
vp++;
}

return cost;
}

public static void main(String[] args) {
int n = 4, m = 5;
Integer[] costVer = {2, 1, 3, 1}; // m-1 cuts
Integer[] costHor = {4, 1, 2}; // n-1 cuts

int totalCost = minCostOfCuttingChocolate(costVer, costHor);
System.out.println("Cost = " + totalCost);
}
}

Loading