-1

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

有袋子承载 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 点的行程？

可以应用什么逻辑？

4

2 回答 2

3

一种方法是遍历排序列表并始终首先选择最大的数字。

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

由于最大的数字应该始终是最难“配对”的，因此这应该为您提供最佳的旅行次数。

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

这是一个简单的实现：

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

于 2021-03-01T09:47:24.457 回答
0

我在这里使用了贪婪的方法，即对权重数组进行排序，并将最重的与最轻的和较轻的组合在一起，直到达到极限。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)

于 2021-03-01T09:27:45.390 回答