CPH Solution (10.5)

Explanation

We solve the problem using dynamic programming with bitmasking to determine the minimum number of elevator rides required to transport all the people within the given weight limit.

We use a DP array where each element corresponds to a bitmask representing which people have already been transported. Each entry in the DP array stores a pair that represents the state of the rides, including the number of rides taken and the weight of the current ride. The bitmask allows us to efficiently represent subsets of people, with each bit indicating whether a specific person has already been transported.

For each subset of people, we iterate over all individuals to determine who could be the last person added to the group. By removing that person from the current subset, we calculate the state of the group without them. If adding this person’s weight to the current ride does not exceed the elevator’s weight limit, we update the total weight for that ride. Otherwise, we start a new ride, incrementing the number of rides, and set the total weight to this person’s weight. After every iteration, we update the state only if the new configuration results in fewer rides or a lighter current total weight.

Finally, when we have transported everyone, the result for the full group is stored in the DP array. This value represents the minimum number of elevator rides needed to transport all the people within the weight limit.

Implementation

Time Complexity: $\mathcal{O}(N\cdot 2^N)$

Copy
import java.io.*;
import java.util.*;

public class ElevatorRides {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int people = io.nextInt();
		int maxWeight = io.nextInt();

		int[] weight = new int[people];

Copy
 Code Snippet: C++ Short Template (Click to expand)

int main() {
	int people, max_weight;
	cin >> people >> max_weight;
	vector<int> weight(people);
	for (int &i : weight) cin >> i;

	vector<pair<int, int>> dp(1 << people, {people + 1, max_weight + 1});
	dp[0] = make_pair(1, 0);

Copy
people, max_weight = map(int, input().split())
weight = list(map(int, input().split()))

dp = [(people + 1, max_weight + 1)] * (1 << people)
dp[0] = (1, 0)

"""
Loop through all bitmasks.
The bitmasks represent whether each person has used the elevator or not.
If the ith bit is set, this means the ith person has used the elevator.