-1

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?

Biku7
  • 450
  • 6
  • 16
  • 3
    Sorry, the point of Stackoverflow is not to write your code for you. You need to try something, show your attempts and your efforts, and if you're stuck somewhere in particular, we can then help you to make your code work. But you can't just come here and say "Here's a problem, please write the solution." – Jeremy Thille Mar 01 '21 at 08:50
  • yes I have tried. I will post my answer. – Biku7 Mar 01 '21 at 09:01
  • Please read about "Knapsack problem" https://en.wikipedia.org/wiki/Knapsack_problem#:~:text=The%20knapsack%20problem%20is%20a,is%20as%20large%20as%20possible. – kelvin Mar 01 '21 at 09:26

2 Answers2

3

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)));
Emil S. Jørgensen
  • 6,216
  • 1
  • 15
  • 28
0

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)

notnotparas
  • 177
  • 1
  • 11