1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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?) $\endgroup$ – greybeard Apr 19 at 4:37
1
$\begingroup$

I think the following algorithm can work (and is greedy):

  • Put all elements in a priority queue
  • While the priority queue has at least 2 elements, extract the two lowest elements, sum them, then add the sum to the priority queue

It gives a correct order for summing elements to get the minimal overall cost.

$\endgroup$
3
  • $\begingroup$ With a priority queue, are you referring to a Heap (represented by a binary tree) ? $\endgroup$ – Lisandro Di Meo Apr 19 at 0:17
  • $\begingroup$ A priority queue is an abstract data structure. A heap is a possible implementation of a priority queue. $\endgroup$ – Nathaniel Apr 19 at 0:23
  • $\begingroup$ Great. I implemented using that and works perfectly. Thanks :) $\endgroup$ – Lisandro Di Meo Apr 19 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.