Elevator Rides

Explicación

Resolvemos el problema usando programación dinámica con máscaras de bits para determinar el número mínimo de viajes del ascensor requeridos para transportar a todas las personas dentro del límite de peso dado.

Usamos un arreglo de DP donde cada elemento corresponde a una máscara de bits que representa qué personas ya fueron transportadas. Cada entrada del arreglo de DP guarda un par que representa el estado de los viajes, incluyendo el número de viajes realizados y el peso del viaje actual. La máscara de bits nos permite representar de forma eficiente subconjuntos de personas, con cada bit indicando si una persona específica ya fue transportada.

Para cada subconjunto de personas, iteramos sobre todos los individuos para determinar quién podría ser la última persona agregada al grupo. Al quitar a esa persona del subconjunto actual, calculamos el estado del grupo sin ella. Si sumar el peso de esta persona al viaje actual no excede el límite de peso del ascensor, actualizamos el peso total de ese viaje. En caso contrario, empezamos un viaje nuevo, incrementando el número de viajes, y fijamos el peso total al peso de esta persona. Después de cada iteración, actualizamos el estado solo si la nueva configuración resulta en menos viajes o un peso total actual más liviano.

Finalmente, cuando transportamos a todos, el resultado del grupo completo está guardado en el arreglo de DP. Este valor representa el número mínimo de viajes del ascensor necesarios para transportar a todas las personas dentro del límite de peso.

Implementación

Complejidad temporal: $\mathcal{O}(N\cdot 2^N)$

JavaC++Python


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];
		for (int i = 0; i < people; i++) { weight[i] = io.nextInt(); }
 
		/*
		 * dp[bitmask] es el mejor estado actual
		 * en términos del número de viajes usados, y el peso usado en el último
		 * viaje. La máscara de bits se usa para representar si las personas usaron
		 * el ascensor. Si el i-ésimo bit está activado, significa que la i-ésima persona usó
		 * el ascensor.
		 */
		State[] dp = new State[1 << people];
		dp[0] = new State(1, 0);
 
		for (int mask = 1; mask < (1 << people); mask++) {
			dp[mask] = new State(people + 1, maxWeight + 1);
			for (int i = 0; i < people; i++) {
				// la i-ésima persona usó el ascensor.
				if ((mask & (1 << i)) > 0) {
					/*
					 * El estado previo de cuando la
					 * i-ésima persona no había usado el ascensor.
					 */
					int prev = mask ^ (1 << i);
					State cur = new State(dp[prev].rides, dp[prev].weight);
					// Hay que usar un viaje nuevo.
					if (cur.weight + weight[i] > maxWeight) {
						cur.rides++;
						cur.weight = Integer.min(weight[i], cur.weight);
					} else {
						// Sumar el peso de la i-ésima persona al viaje actual.
						cur.weight += weight[i];
					}
					// Comprobar si es mejor que el original.
					if (cur.compareTo(dp[mask]) < 0) { dp[mask] = cur; }
				}
			}
		}
		// Resultado cuando todas las personas usaron el ascensor.
		io.println(dp[(1 << people) - 1].rides);
		io.close();
	}
 
	// El estado (i,j) significa que estamos en el i-ésimo viaje, y usamos j de peso.
	static class State {
		public int rides, weight;
 
		public State(int rides, int weight) {
			this.rides = rides;
			this.weight = weight;
		}
 
		public int compareTo(State oState) {
			if (this.rides == oState.rides) {
				return Integer.compare(this.weight, oState.weight);
			}
			return Integer.compare(this.rides, oState.rides);
		}
	}
 
	// CodeSnip{Kattio}
}


// CodeSnip{CPP Short Template}
 
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);
	/*
	 * Recorrer todas las máscaras de bits.
	 * Las máscaras representan si cada persona usó el ascensor o no.
	 * Si el i-ésimo bit está activado, esto significa que la i-ésima persona usó el ascensor.
	 */
	for (int mask = 1; mask < (1 << people); mask++) {
		for (int i = 0; i < people; i++)
			// La i-ésima persona usó el ascensor.
			if (mask & (1 << i)) {
				auto prev = dp[mask ^ (1 << i)];
				int num_rides = prev.first;
				int total_weight = prev.second;
				// Hay que usar un viaje nuevo.
				if (total_weight + weight[i] <= max_weight) total_weight += weight[i];
				else {
					// Sumar el peso de la i-ésima persona al viaje actual.
					num_rides++;
					total_weight = weight[i];
				}
				// Actualizar si es mejor que el original.
				dp[mask] = min(dp[mask], make_pair(num_rides, total_weight));
			}
	}
	// Resultado cuando todas las personas usaron el ascensor.
	cout << dp[(1 << people) - 1].first;
}


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)
 
"""
Recorrer todas las máscaras de bits.
Las máscaras representan si cada persona usó el ascensor o no.
Si el i-ésimo bit está activado, esto significa que la i-ésima persona usó el ascensor.
"""
 
for mask in range(1, 1 << people):
	for i in range(people):
		# La i-ésima persona usó el ascensor
		if mask & (1 << i):
			prev = dp[mask ^ (1 << i)]
			num_rides = prev[0]
			total_weight = prev[1]
 
			# Hay que usar un viaje nuevo
			if total_weight + weight[i] <= max_weight:
				total_weight += weight[i]
 
			else:
				# Sumar el peso de la i-ésima persona al viaje actual
				num_rides += 1
				total_weight = weight[i]
 
			# Actualizar si es mejor que el original
			dp[mask] = min(dp[mask], (num_rides, total_weight))
 
# Resultado cuando todas las personas usaron el ascensor
print(dp[(1 << people) - 1][0])