38. UVa-624 CD //Easy recursive Backtracking

문제

 

Input이 저렇게 주어질 때 저장용량에 들어갈 수 있는 곡들의 조합 중 가장 저장용량을 꽉 채울 수 있는 곡들의 조합과 그 용량을 출력하는 문제다.

 

이 문제는 Input의 크기가 작아서 그냥 recursive backtracking기법을 써서 완전탐색으로 풀었다. 근데 아직 재귀적 탐색이 익숙치가 않아서 별로 효율적이지 않을 수도 있다.

다음은 코드다.

#include<iostream>
using namespace std;
int maximum = 0;
int N, num_of_tracks;
int time_of_tracks[20];
int Choice[20];
int BestChoice[20];
int max_choice_num;
void Backtracking(int c, int num_of_choices, int curr_cap) {   //c-1번 track까지는 이미 다 봤음
	if (c == num_of_tracks) return;   //더 이상 볼 게 없는 경우

	//이제 c번째거도 가능하면 추가시키는 경우를 생각해보자.
	//c+1번째 거를 추가 가능한지보자. 추가 가능한 경우에만 추가해서 진행하면 된다.
	if (curr_cap + time_of_tracks[c] <= N) {
		//추가 가능한 경우 Backtracking을 진행하되 max갱신을 하자
		Choice[num_of_choices] = time_of_tracks[c];
		if (curr_cap + time_of_tracks[c] > maximum) {
			maximum = curr_cap + time_of_tracks[c];
			max_choice_num = num_of_choices + 1;
			//여기에 Choice를 BestChoice로써 메모하기
			for (int i = 0; i < max_choice_num; i++) {
				BestChoice[i] = Choice[i];
			}
		}
		Backtracking(c + 1, num_of_choices + 1, curr_cap + time_of_tracks[c]);
	}
	Backtracking(c + 1, num_of_choices, curr_cap);   //아무것도 안보고 진행시키는 경우
}

int main() {
	while (cin >> N) {
		cin >> num_of_tracks;
		for (int i = 0; i < num_of_tracks; i++) cin >> time_of_tracks[i];
		maximum = 0;
		Backtracking(0, 0, 0);

		for (int i = 0; i < max_choice_num; i++) {
			cout << BestChoice[i] << " ";
		}
		cout << "sum:" << maximum << endl;
	}

	return 0;
}

if(curr_cap+time_of_tracks[c]<=N) 부분에서 가지치기를 한 번 수행하는 코드다. 참고로 이 문제는 Input의 크기가 작아서 완전탐색으로 풀어도 0.000초에 AC판정이 나온다..