gpt4 book ai didi

algorithm - 有趣的算法任务——电梯

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:46:28 27 4
gpt4 key购买 nike

它类似于背包问题,但更复杂。

A到B有电梯,1趟价格如下:

1) 如果只有一个人 - 以美分为单位的高度 - 如果 180 -> 180 美分

2) 如果超过一个人 -> 最大高度:[180, 150, 185] -> 总共 185 美分。

电梯的极限是N公斤大于等于700——比如700kg。

你有 N 个客户,有 kg 和高度,例如:

[{h: 180, w: 70}, {h: 180, w: 60},...]

任务是计算将所有客户从 A 运送到 B 的最低成本。

我目前的解决方案:

我得到了可用的组合。

如果我有 5 个客户:[1]、[2]..[5]、[1,2]、[2,3]...[1,2,3]...,[1, 2,3,4,5]

现在的问题是我有 255 个组合(对于 N 个人)。

我以为我可以让所有组合计算最低价格,检查每次行程中的公斤数是否不超过最大公斤容量并像这样返回:

每个嵌套数组都是一次旅行中的人

[[1],[2],[3],[4],[5]] - 每个人在单独的行程中[[1], [2,3,4,5] - 一种组合

[[1], [2], [3,4,5]] - 秒[[1], [2], [3], [4], [5]]

然后计算每一行,然后很容易 - 排序并返回第一行。

对于 5 个客户端,这工作正常,但对于 20 个,组合是巨大的,无法在可接受的时间内计算。

你能帮我指点或完整的解决方案吗?

谢谢:)

最佳答案

您可以使用 dijkstra,其中每个状态都是剩下的人。我们可以用一个位掩码来表示还需要去指定楼层的人,第 i 个位置的 1 表示第 i 个人已经去了指定楼层。

转换意味着与仍然需要前往所需楼层的一组人一起旅行,从而将状态更改为在该旅行中的每个人的第 i 个位置都有一个 1。因为有 20 个客户端,所以有 2^20 种可能的状态。这是我在 c++ 中提出的 dijkstra 解决方案,最多支持 20 人。

#include <iostream>
#include <vector>
#include <set>
#include <map>

using namespace std;

struct Person {
int weigth;
int height;

Person (int w, int h) {
weigth = w;
height = h;
}
};

set<pair<int, int> > s;
int maxWeigth = 200;
vector<Person> persons;
int distances[1 << 21];
int currentCost;

void visitNeighbors(vector<int>& remainingPersons, int state, int weigthSum, int maxHeight, int index) {
if (weigthSum > maxWeigth) return;

if (index != 0) {
if (distances[state] == -1 || currentCost + maxHeight < distances[state]) {
distances[state] = currentCost + maxHeight;
s.insert(make_pair(distances[state], state));
}
}

if (index == remainingPersons.size()) return;

visitNeighbors(remainingPersons, state | (1 << remainingPersons[index]), weigthSum + persons[index].weigth, max(maxHeight, persons[index].height), index + 1);
visitNeighbors(remainingPersons, state, weigthSum, maxHeight, index + 1);
}

int main () {
persons.push_back(Person(90, 170));
persons.push_back(Person(80, 160));
persons.push_back(Person(100, 150));

fill(distances, distances + (1 << 21), -1);

int target = (1 << (persons.size())) - 1; // 111 means the 3 persons have already arrived at desired floor

s.insert(make_pair(0, 0)); // initial state is with 0 cost and no person on the desired floor
distances[0] = 0;

while (!s.empty()) {
pair<int, int> p = *s.begin();
s.erase(s.begin());

currentCost = p.first;
int state = p.second;

vector<int> remainingPersons;


if (distances[state] != -1 && distances[state] < currentCost) continue;
if (state == target) break;


for (int i = 0; i < persons.size(); i++) {
if ((state & (1 << i)) == 0) { // if we have a 0 at index i on state as a binary string, we still need to move that person
remainingPersons.push_back(i);
}
}

visitNeighbors(remainingPersons, state, 0, 0, 0);
}

cout << distances[target] << endl;

}

JS 实现:

var maxWeigth = 200;

var persons = [{
height: 170,
weigth: 90
},
{
height: 160,
weigth: 80
},
{
height: 150,
weigth: 100
}];

var distances = new Array(1 << persons.length);
distances.fill(-1);

var currentCost;

var target = (1 << persons.length) - 1;

var queue = new PriorityQueue({ comparator: (a, b) => a.cost - b.cost});

queue.queue({cost: 0, mask: 0});
distances[0] = 0;

while(queue.length) {
var state = queue.dequeue();

if (distances[state.mask] != -1 && distances[state.mask] < state.cost) continue;
if (state.mask == target) break;

var remainingPersons = []
currentCost = state.cost;

for (var i = 0; i < persons.length; i++) {
if ((state.mask & (1 << i)) == 0) {
remainingPersons.push(i);
}
}

visitNeighbors(remainingPersons, state.mask, 0, 0, 0);
}

console.log(distances[target])


function visitNeighbors(remainingPersons, mask, weigthSum, maxHeight, index) {
if (weigthSum > maxWeigth) return;

if (index != 0) {
if (distances[mask] == -1 || currentCost + maxHeight < distances[mask]) {
distances[mask] = currentCost + maxHeight;
queue.queue({cost: distances[mask], mask: mask});
}
}

if (index == remainingPersons.length) return;

visitNeighbors(remainingPersons, mask | (1 << remainingPersons[index]), weigthSum + persons[index].weigth, Math.max(maxHeight, persons[index].height), index + 1);
visitNeighbors(remainingPersons, mask, weigthSum, maxHeight, index + 1);
}
<script src="https://cdn.rawgit.com/adamhooper/js-priority-queue/master/priority-queue.min.js"></script>

关于algorithm - 有趣的算法任务——电梯,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50992881/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com