문제

출처 : https://www.algospot.com/judge/problem/read/PACKING

여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 캐리어를 하나만 가지고 갈 수 있는데, 아무래도 가져가고 싶은 물건들이 캐리어 안에 다 들어가지 않을 것 같습니다. 재훈이는 가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를 조사해 다음과 같은 목록을 만들었습니다.

캐리어의 용량이 정해져 있기 때문에 가져갈 수 있는 물건들의 부피 합은 캐리어의 용량 w 이하여야 합니다. 이때 절박도를 최대화할 수 있는 물건들의 목록을 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1≤C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 가져가고 싶은 물건의 수 N (1≤N≤100)과 캐리어의 용량 W (1≤W≤1000)가 주어집니다. 그 이후 N줄에 순서대로 각 물건의 정보가 주어집니다. 한 물건에 대한 정보는 물건의 이름, 부피, 절박도 순서대로 주어지며, 이름은 공백 없는 알파벳 대소문자 1글자 이상 20글자 이하의 문자열, 부피와 절박도는 1000 이하의 자연수입니다.

출력

각 테스트 케이스별 출력의 첫 줄에는 가져갈 수 있는 물건들의 최대 절박도 합과 가져갈 물건들의 개수를 출력합니다. 이후 한 줄에 하나씩 각 물건들의 이름을 출력합니다. 만약 절박도를 최대화하는 물건들의 조합이 여럿일 경우 아무 것이나 출력해도 좋습니다.

풀이

유명한 알고리즘인 냅색 알고리즘을 사용하여 푸는 0-1 배낭 문제이다. 함수는 다음과 같다.

// 남은 용량이 s일 때 t번 이전 물건들을 담아 얻을 수 있는 최대 절박도
// bag[i][0] : i번째 물건의 무게, bag[i][1] : i번째 물건의 가치
	static int knapsack(int t, int s) {
		if (t == 0)
			return 0;
		if (cache[t][s] != -1)
			return cache[t][s];
		int ret = 0;
		if (s >= bag[t][0])
			ret = Math.max(knapsack(t - 1, s), bag[t][1] + knapsack(t - 1, s - bag[t][0]));
		else
			ret = knapsack(t - 1, s);
		cache[t][s] = ret;

		return ret;
	}

문제를 조각내어 생각할 때, 배낭에 최대 무게를 담기 위해서는 현재 물건의 무게와 가치를 고려하여 넣을지 말지를 판단하여야 한다. i번째 물건에 대해 판단할 때, 이 물건을 담고 물건만큼의 무게가 줄어들었을 떄 나머지를 채우는 경우와 이 물건을 담지않고 남은 무게그대로 나머지 물건을 담는 경우를 비교하여 최대가 되는 경우를 선택하여야 한다. 따라서, 특정 물건번호를 선택하면 해당 물건번호의 이전 물건들을 각각 위의 경우로 대입하여 두 경우를 비교하되, 배낭의 현재 무게를 매개변수로 하여 물건이 선택된 경우 무게 매개변수에 해당 물건의 무게를 빼서 남은 용량을 고려하여야 한다.

물건을 넣기 전에 현재 용량을 고려하여 넣으려는 물건의 무게가 용량보다 작은지 비교하고, 작은 경우 위의 경우대로 비교하고, 담지 못할 경우 다음 물건부터 고려하도록 재귀호출한다. 이를 통해 전체 물건에 대하여 주어진 최대 용량에 대해 최대 가치를 얻을 수 있는 경우를 얻을 수 있다.

이 문제는 이에 더하여 어떠한 물건을 담았는지도 출력하여야 하는데, 최대 가치만큼 담을 때 들어간 물건을 기록하는 방법은 위의 함수 knapsack(t,s)에서(t번 이하 번호의 물건들을 s용량 가방에 담는 경우) t번째 물건을 담는 경우를 생각할 때, 만약 해당 물건이 담기지 않았다면 knapsack(t-1,s) 값(t-1번 이하 번호의 물건들을 s용량 가방에 담는 경우)값과 같으므로 이를 검사하여 물건이 담긴 여부를 파악할 수 있다. 만약 담긴 경우, 위의 재귀함수처럼 남은 용량에 담긴 무게를 뺴주어 다음 경우를 고려할 수 있다.

따라서 추적 함수도 마찬가지로 knapsack함수를 호출하여 물건의 담김 여부를 비교하면서 담겼을 경우 해당 이름을 스택에 넣어서 다음과 같이 기록할 수 있다.

static void reconstruct(int t, int s) {
		if(t==0)
			return;
		if(knapsack(t,s)==knapsack(t-1,s))
			reconstruct(t-1,s);
		else {
			picked.push(nametag[t]);
			reconstruct(t-1,s-bag[t][0]);
		}
	}