How to find minimum number of trips to do in order to complete this work from point A to point B using javascript?

Question

So I am solving this problem given as:

There are bags carrying weights from 1 to 3 units and I have to carry them from point A to point B. Weights are given of bags in array. All weights are less than 3 unit.

weights = [1, 1.78, 2.2, 2.73, 3]

So I have to make the trips carrying the bags should not cross the total weight greater than 3 unit. In order to that I have to make minimum number of trips.

Example: weights = [1.01, 1.99, 2.5, 1.5, 1.01]

I can carry all bags in 3 trips minimum as:

[1.01 + 1.99, 2.5, 1.5 + 1.01].

Means how to determine the minimum no. of trips to carry the weight bags from point A to point B?

What logic can be applied?

Answer 1

One approach is to loop through a sorted list and always pick out the biggest number first.

Then you loop through the remaining elements and combine it with the largest number, where the combined sum is less than your target.

Since the largest number should always be the hardest to "pair", this should give you the optimal number of trips.

However this approach doesn't distribute weight evenly. It will favor packing pairs as big as possible.

Here is a simple implementation:

function SplitToBalancedPairs(inputs, target) {
    let outputs = [];
    inputs = inputs.slice(0).sort((a, b) => a - b);
    while (inputs.length > 0) {
        let a = inputs.pop();
        let b;
        let c;
        for (let i = 0; i < inputs.length; i++) {
            b = inputs[i];
            if (a + b <= target) {
                c = i;
                break;
            }
        }
        if (c !== void 0) {
            outputs.push([a, inputs.splice(c, 1).pop()]);
        }
        else {
            outputs.push([a]);
        }
    }
    return outputs;
}
//Test
let weights = [1, 1.78, 2.2, 2.73, 3];
let results = SplitToBalancedPairs(weights, 3);
console.log(results);
console.log(results.map(a => a.reduce((b, c) => b + c)));

Answer 2

I've used greedy approach here, which is to sort the weights array, and combine the heaviest one with lightest and lighter ones until we reach the limit. Python code:

def solve(A):
    A.sort()  
    n = len(A)
    i =0
    j = n-1
    ans=0
    while i<=j: 
        while A[i]+A[j] <=3: 
            i+=1
        ans+=1
        j-=1
  
    return ans 

print(solve([1.01, 1.99, 2.5, 1.5, 1.01]))

Time Complexity: O(n)