有趣的算法任务 - 电梯

Question

这类似于背包问题，但更加复杂。

有一台电梯从A到B。1次行程的价格如下：

1）如果只有一个人-身高为180厘米-如果是180 -> 180分。

2）如果有多个人->最大身高：[180,150,185]->总共185分。

电梯的限制是N公斤，大于或等于700公斤-例如700kg。 你有N个客户，他们有千克和身高，例如： [{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个客户，组合是巨大的，并且无法在可接受的时间内计算。

你能帮我指导或提供完整的解决方案来解决这个任务吗？

谢谢:)

- user2693928

---

1个人的价格是他的身高（厘米）对应的分数：180 -> 180分。如果有多个客户，旅行的总价是最高的那个人的身高：[180, 150, 185] - 旅行的总价是185分。 - user2693928

我有20个客户，他们的身高和体重是随机的，身高在150-200之间，体重在50-150公斤之间：[{h: 190, w: 80}, {h: 180, w: 65}....] - user2693928

如果我最大化这次旅行，下一次旅行就无法优化，所以第一次是可以的，但应该还有两次旅行。而且可能只需要两次旅行就能找到解决方案。 - user2693928

旅行次数并不重要，您只需要最小化成本，这是状态之间边缘成本的总和。而Dijkstra算法只会访问每个状态一次。 - juvian

请给我一个包含20个用户的测试用例。 - juvian

Answer 1

您可以使用迪杰斯特拉算法，其中每个状态表示剩余的人。我们可以使用位掩码来表示仍需要前往所需楼层的人员，第i个位置上的1表示第i个人已经去到了所需的楼层。

一次转换意味着与仍需要前往所需楼层的一组人进行旅行，从而改变状态以使每个参与此次旅行的人在第i个位置上都有一个1。由于有20个客户端，因此存在2^20种可能的状态。这是我在C ++中提出的迪杰斯特拉解决方案，支持最多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;

}

JavaScript实现：

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>

- juvian

---

在你的答案中，解释一下问题是如何被建模的可能会很好。 - גלעד ברקן

@גלעדברקן 添加了 - juvian

这是一个答案，但显然不是最优解 - 它是背包问题的贪心解决方案。实际的搜索空间，对于最优解来说不是“A楼层上的人，B楼层上的人”。它是人数的分区集合，对于20个人而言，这个数量远远超过2^20。 - spinkus

@spinkus，你能给出一个实际的例子，其中真实解决方案与我的输出不同吗？ - juvian

嗯，你的代码只是打印了一个数字而不是解决方案，所以一眼看去很难确定它在做什么。 - spinkus

@spinkus 在背包问题中，您想要最大化利润，而在这里我们想要最小化。至于实际的搜索空间，您有很多重复的状态。与人1一起旅行，然后与2、3一起旅行，与1一起旅行，然后与2、3一起旅行是相同的。与2一起旅行，然后与1、3一起旅行是成立的，但是使用Dijkstra算法，我正在最小化到达1、2和3到达所需楼层的成本。 - juvian