[알고리즘/C++] 동적 계획법 - 엘리베이터 운행횟수

엘리베이터에는 한번에 탑승 가능한 무게 제한이 있다. 

 

엘리베이터에 탑승하기 위한 승객들이 대기하고 있고, 무게 제한을 만족하면서

 

최소한의 운행 횟수로 승객들을 운반해야한다. 

 

가장 작은 운행 횟수를 구하는 문제를 동적 계획법으로 해결해보자.

 

	vi weight = { 86, 58, 76, 102, 91 };
	int lim = 200;

input 값으로 승객들의 무게 데이터와 엘리베이터의 무게 제한이 주어진다. 

 

pair<int, int> best[1 << 5];

 

5명의 승객에 대한 탑승 정보 데이터를 담는 pair 배열을 선언한다. 

 

5명의 승객에 대한 탑승 경우의 수에 대한 부분 집합은 총 2^5(=32)개의 케이스가 나온다. 

 

따라서 32개의 각 케이스에 대한 최소 운행 횟수(int), 마지막 운행의 승객 무게 총합(int)를 담는 pair가 필요하다. 

 

void elevatorRides(vi weight, int lim) {
	for (int s = 1; s < (1 << weight.size()); s++) {
		// 원소 갯수 n일 때 부분집합의 경우의 수: 2^n
		best[s] = { weight.size() + 1, 0 };
		for (int p = 0; p < weight.size(); p++) {
			//모든 passenger에 대해서 순회
			if (s & (1 << p)) {
				// 현재 승객(p)이 부분집합 s에 포함되어있다면
				auto option = best[s ^ (1 << p)];
				//s에서 p가 빠진 케이스
				if (option.first == 0) {
					//p가 없는 케이스가 운행횟수가 0이라면
					//그 케이스는 공집합이므로 
					option.first++;
					//운행횟수를 추가
				}
				if (option.second + weight[p] <= lim) {
					//p를 태울 수 있다면
					option.second += weight[p];
					//p를 태운다. (운행횟수는 증가X)
				}
				else {
					option.first++;
					// p를 못태우면 운행횟수 증가 필요
					option.second = weight[p];
					//마지막 승객은 p
				}
				best[s] = min(best[s], option);
			}
		}
	}
	return;
}

best를 갱신하는 전체 코드이다. 

 

	for (int s = 1; s < (1 << weight.size()); s++) {
		// 원소 갯수 n일 때 부분집합의 경우의 수: 2^n
		best[s] = { weight.size() + 1, 0 };

먼저 가능한 부분 집합들의 모든 경우의 수를 순회하고, 각 케이스에 대한 초기값은 (모든 승객수+1, 0)로 초기화한다. 

 

		for (int p = 0; p < weight.size(); p++) {
			//모든 passenger에 대해서 순회
			if (s & (1 << p)) {
				// 현재 승객(p)이 부분집합 s에 포함되어있다면

그리고 각 승객 한명 한명에 대한 순회를 진행한다. 

 

비트 연산을 통해 현재 승객(p)이 부분집합(s)에 포함되어 있는지 확인한다. 

 

예를 들어 현재 s가 12이라면 0 1 1 0 0 이므로 3번째 승객과 4번째 승객 이 포함되어 있다. 

 

				auto option = best[s ^ (1 << p)];
				//s에서 p가 빠진 케이스

그렇다면 그 승객 p가 현재 부분 집합에서 제외된 경우를 살펴본다. 

 

				if (option.first == 0) {
					//p가 없는 케이스가 운행횟수가 0이라면
					//그 케이스는 공집합이므로 
					option.first++;
					//운행횟수를 추가
				}

승객 p가 제외된 부분집합에서 운행횟수가 0라면 최소한 한번은 운행을 해야하므로 option의 운행횟수를 하나 늘려준다. 

 

				if (option.second + weight[p] <= lim) {
					//p를 태울 수 있다면
					option.second += weight[p];
					//p를 태운다. (운행횟수는 증가X)
				}

 해당 케이스의 second(마지막 운행의 승객 무게 총합)의 값을 보고 승객 p가 부분집합에 추가되어도 

 

무게 제한을 만족하는지 살펴보고 탑승 가능한 경우에 option의 second에 현재 승객 p의 무게를 추가한다. 

 

				else {
					option.first++;
					// p를 못태우면 운행횟수 증가 필요
					option.second = weight[p];
					//마지막 승객은 p
				}

만약 무게 제한을 넘어서면 그 승객(p)는 다음 번 운행에 탑승해야하므로 탑승 횟수(first)를 늘려주고 

 

second에는 p의 무게로 갱신한다.

 

option은 단순히 값을 복사해온것이기 때문에 실제로 best에 대한 갱신은 이루어지지 않는다.

				best[s] = min(best[s], option);

그러고 나서 갱신된 option의 값과 best[s]의 값을 비교하여 작은 값으로 갱신한다. 

 

	vi weight = { 86, 58, 76, 102, 91 };
	int lim = 200;
	elevatorRides(weight, lim);
	for (int i = 1; i < 32; i++) {
		displayPassenger(maskPassenger(i, weight), weight);
		cout << "minimum ride number: "<< best[i].first << " | last passengers weight: " << best[i].second << "\n";
	}

계산된 결과이다. 

 

void displayPassenger(vector<bool> mask, vi weight) {
	cout << "\npassengers Weights(kg): ";
	for (int i = 0; i < mask.size(); i++) {
		if (mask[i] == true) {
			cout << weight[i] << " ";
		}
	}
	cout << "\n";
}

 

passengers Weights(kg): 86
minimum ride number: 1 | last passengers weight: 86

passengers Weights(kg): 58
minimum ride number: 1 | last passengers weight: 58

passengers Weights(kg): 86 58
minimum ride number: 1 | last passengers weight: 144

passengers Weights(kg): 76
minimum ride number: 1 | last passengers weight: 76

passengers Weights(kg): 86 76
minimum ride number: 1 | last passengers weight: 162

passengers Weights(kg): 58 76
minimum ride number: 1 | last passengers weight: 134

passengers Weights(kg): 86 58 76
minimum ride number: 2 | last passengers weight: 58

passengers Weights(kg): 102
minimum ride number: 1 | last passengers weight: 102

passengers Weights(kg): 86 102
minimum ride number: 1 | last passengers weight: 188

passengers Weights(kg): 58 102
minimum ride number: 1 | last passengers weight: 160

passengers Weights(kg): 86 58 102
minimum ride number: 2 | last passengers weight: 58

passengers Weights(kg): 76 102
minimum ride number: 1 | last passengers weight: 178

passengers Weights(kg): 86 76 102
minimum ride number: 2 | last passengers weight: 76

passengers Weights(kg): 58 76 102
minimum ride number: 2 | last passengers weight: 58

passengers Weights(kg): 86 58 76 102
minimum ride number: 2 | last passengers weight: 134

passengers Weights(kg): 91
minimum ride number: 1 | last passengers weight: 91

passengers Weights(kg): 86 91
minimum ride number: 1 | last passengers weight: 177

passengers Weights(kg): 58 91
minimum ride number: 1 | last passengers weight: 149

passengers Weights(kg): 86 58 91
minimum ride number: 2 | last passengers weight: 58

passengers Weights(kg): 76 91
minimum ride number: 1 | last passengers weight: 167

passengers Weights(kg): 86 76 91
minimum ride number: 2 | last passengers weight: 76

passengers Weights(kg): 58 76 91
minimum ride number: 2 | last passengers weight: 58

passengers Weights(kg): 86 58 76 91
minimum ride number: 2 | last passengers weight: 134

passengers Weights(kg): 102 91
minimum ride number: 1 | last passengers weight: 193

passengers Weights(kg): 86 102 91
minimum ride number: 2 | last passengers weight: 86

passengers Weights(kg): 58 102 91
minimum ride number: 2 | last passengers weight: 58

passengers Weights(kg): 86 58 102 91
minimum ride number: 2 | last passengers weight: 144

passengers Weights(kg): 76 102 91
minimum ride number: 2 | last passengers weight: 76

passengers Weights(kg): 86 76 102 91
minimum ride number: 2 | last passengers weight: 162

passengers Weights(kg): 58 76 102 91
minimum ride number: 2 | last passengers weight: 134

passengers Weights(kg): 86 58 76 102 91
minimum ride number: 3 | last passengers weight: 58