# Find the minimum cost of adding the elements of a set (greedy algorithm)

I'm VERY stuck with this problem:

Given a set (with possible repeated elements), the cost of adding two elements $$x, y$$ is $$x + y$$. For example, the possible costs of the next set $$\{1,2,5 \}$$ are:

• The cost of adding $$1 + 2$$ (with cost $$3$$), plus the cost of $$3 + 5$$ (with cost $$8$$). The overall cost is $$11$$.
• The cost of adding $$1 + 5$$ (with cost $$6$$), plus the cost of $$6 + 2$$ (with cost $$8$$). The overall cost is $$14$$.
• The cost of adding $$2 + 5$$ (with cost $$7$$), plus the cost of $$7 + 1$$ (with cost $$8$$). The overall cost is $$15$$.

We want to find the minimum overall cost (implementing a greedy-algorithm).

I've implemented two approaches:

const minCost = (l = []) => {
sort(l);
let cost = 0;
let currentSum = 0;
for(let i = 0; i < l.length - 1; i++){
if(i === 0){
currentSum = l[i] + l[i + 1];
cost += currentSum;
}
else{
currentSum += l[i + 1];
cost += currentSum;
}
}
return cost;
}


What im doing here is sorting in ascending order, and then simply computing the costs (like the first option in the example).

The issue I found is with the following instance: [2,2,2,2] will compute a cost of 18. But, I've realized that you can group the elements and compute the cost of the in this way: ((2+2) + (2+2)), with overall cost of 16.

So I also came out with this approach:

const cost = (l = []) => {
if(l.length <= 1) return 0
else return l.reduce((acc, val) => acc + val, 0)
}

const minCostRecursive = (l = []) => {
if(l.length <= 2) return cost(l)
let left = minCostRecursive([...l.slice(0, Math.ceil(l.length/2) )])
let right = minCostRecursive([...l.slice(Math.ceil(l.length/2), l.length)])
let newList = []
left > 0 ? newList.push(left) : newList.push(...l.slice(0, Math.ceil(l.length/2)))
right > 0 ? newList.push(right) : newList.push(...l.slice(Math.ceil(l.length/2), l.length))
return left + right + minCostRecursive(newList)
}


The main idea is to partition the cost of the halves. If you have two items, the cost is the sum of the items. If you have one or fewer items, the cost is 0 (there is nothing to add). If not, I make a recursive call to the function with the halves, and with if its result is greater than zero, then I add it to a new list. If not, I add the element that was there before, and call the function again.

But also, I found a counterexample [1,5,7,9] (in the first implementation it gives 41, but in the second returns 44). Moreover, I think this isn't a greedy solution.

• Welcome to COMPUTER SCIENCE @SE. I think you did well analysing the examples you present. Using more examples, you would (re)discover a well-known algorithm. (Not too sure about greedy - mind to include a definition for the context of this question?) Apr 19, 2021 at 4:37