如何使用 javascript 找到完成从 A 点到 B 点的这项工作的最少行程次数？

Question

所以我正在解决这个问题：

有些袋子的重量从 1 到 3 个单位不等，我必须将它们从 A 点搬运到 B 点。重量由数组中的袋子给出。所有重量都小于3个单位。

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

所以我要使旅行携带的行李总重量不要超过3个单位。为此，我必须进行最少的行程。

示例： 权重 = [1.01, 1.99, 2.5, 1.5, 1.01]

我至少可以携带所有行李 3 次：

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

表示如何确定最小编号。从 A 点到 B 点携带重量袋的行程？

可以应用什么逻辑？

Answer 1

这里我用了贪心的方法，就是对weights数组进行排序，把最重的和最轻的结合起来，直到达到极限。 Python代码：


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]))

时间复杂度：O(n)

Answer 2

一种方法是遍历一个排序列表，总是先选出最大的数字。

然后循环遍历剩余的元素并将其与最大数组合，组合总和小于目标。

因为最大的数字应该总是最难“配对”的，这应该会给你最佳的行程数。

然而，这种方法并没有均匀分配权重。它将有利于尽可能大的打包对。

这是一个简单的实现：

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)));

如何使用 javascript 找到完成从 A 点到 B 点的这项工作的最少行程次数？

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

javascript

arrays

logical-reads