Interesting algorithm task - elevator

Question

Its similar to knapsack problem but more complex.

There is an elevator from A to B. The price for 1 trip is as follows:

1) If only one person - height in cents - if 180 -> 180 cents

2) If more than one person -> height of the maximum: [180, 150, 185] -> 185 cents total.

The limit of the elevator is N kg bigger or equal to 700 - for example 700kg.

You have N clients with kg and height, for example:

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

The task is to calculate the minimum cost to transport all the clients from A to B.

My solution so far:

I get the available combinations.

If i have 5 clients: [1], [2]..[5], [1,2], [2,3]...[1,2,3]...,[1,2,3,4,5]

Now the problem is that i have 255 combinations (for N people).

I thought i could get all the combinations calculate the min price, check if kgs in each trip not exceed the max kg capacity and return it like this:

Each nested array are people in one trip

[[1],[2],[3],[4],[5]] - each person in separate trip [[1], [2,3,4,5] - one combination

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

Then calculate each row and from then its easy - sort and return the first one.

For 5 clients this works ok, but for 20 the combinations are huge and unavailable to calculate in acceptable time.

Can you help me with directions or full solution how to solve the task.

Thank you:)

Answer 1

You can use dijkstra, where each state is which persons are left. We can use a bitmask to represent the persons that still need to go to the desired floor, a 1 in the ith position means the ith person already went to the desired floor.

A transition means doing a trip with a set of people that still need to go to the desired floor, thus changing the state to have a 1 in the ith position for every person that went in that trip. As there are 20 clients, there are 2^20 possible states. Here is the dijkstra solution I proposed in c++, supports up to 20 persons.

#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 Implementation:

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>