您可以使用迪杰斯特拉算法,其中每个状态表示剩余的人。我们可以使用位掩码来表示仍需要前往所需楼层的人员,第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;
s.insert(make_pair(0, 0));
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) {
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>