여행 짐 싸기

문제

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

물건	노트북	카메라	xbox	커피 그라인더	아령	백과사전
부피	4	2	6	4	2	10
절박도	7	10	6	7	5	4

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

입력

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

예제 입력 및 출력

입력

2

6 10

laptop 4 7

camera 2 10

xbox 6 6

grinder 4 7

dumbell 2 5

encyclopedia 10 4

6 17

laptop 4 7

camera 2 10

xbox 6 6

grinder 4 7

dumbell 2 5

encyclopedia 10 4

 

출력

24 3

laptop

camera

grinder

30 4

laptop

camera

xbox

grinder

소스 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

int Case;
//cache[capacity][num] - capacity의 용량을 num번 이후의 물건으로 채울때 최대 urgent저장
int cache[1001][100];

// 물건의 정보를 나타내는 구조체
typedef struct object {
	string name; //물건의 이름
	int capacity; //물건의 용량
	int urgent; //절박도
};

class Carrier {
private:
	int capacity;// 가방의 용량
	int num; // 물건의 수
	int packnum; //챙긴 물건의 수
	object* obarr; //물품의 목록을 저장한 배열
	vector<string> package; //챙긴 물건들
public:
	void Input() {
		cin >> num >> capacity; //물건의 개수, 캐리어 용량 입력받기
		obarr = new object[num]; //물건의 정보를 저장할 배열을 할당
		for (int i = 0; i < num; i++)
			cin >> obarr[i].name >> obarr[i].capacity >> obarr[i].urgent;
		packnum = 0;
	}
	void Output() {
		getlist(capacity, 0);
		cout << maxUrgent(capacity, 0) << " " << packnum << endl;
		for (int i = 0; i < packnum; i++)
			cout << package.at(i) << endl;
	}
	//최대 절박도를 구하는 함수
	//rest: 남은용량 obidx: 추가할 물건의 번호
	int maxUrgent(int rest, int obidx) {
		int unpack, pack;
		//함수 탈출 조건 -> 마지막 범위를 벗어난 경우
		if (obidx == num)
			return 0;

		//기저 사례
		if (cache[rest][obidx] != -1)
			return cache[rest][obidx];

		//현재 물건을 넣지 않는다. -> 남은 용량 그대로 다음 물건을 넣을지 확인
		unpack = maxUrgent(rest, obidx + 1);

		//현재 넣으려는 물건의 용량이 남은 캐리어에 넣을 수 있다면 물건을 넣는다.
		if (rest >= obarr[obidx].capacity) 
			pack = maxUrgent(rest - obarr[obidx].capacity, obidx + 1) + obarr[obidx].urgent;
		
		cache[rest][obidx] = max(unpack, pack);
		return cache[rest][obidx];
	}

	//챙긴 물품 목록을 출력하는 함수
	void getlist(int rest, int obidx) {
		if (obidx == num)
			return;
		//현재 짐을 안넣어도 최대절박도가 똑같으면 통과
		if (maxUrgent(rest, obidx) == maxUrgent(rest, obidx + 1))
			getlist(rest, obidx + 1);
		//달라지면 넣는다
		else {
			package.push_back(obarr[obidx].name);
			packnum++;
			getlist(rest - obarr[obidx].capacity, obidx + 1);
		}
	}
};

Carrier* carrier;

int main(void) {

	cin >> Case;
	carrier = new Carrier[Case];

	for (int i = 0; i < Case; i++) 
		carrier[i].Input();
	
	for (int i = 0; i < Case; i++) {
		memset(cache, -1, sizeof(cache));
		carrier[i].Output();
		cout << endl;
	}
}

문제 해설

• 최대 절박도 구하기

  • 물건이 n개가 있다고 할 때 1번~n번까지 물건을 넣을 경우 / 안 넣을 경우 각각 재귀 호출을 한다.

  • 각 함수에서 물건을 넣지 않았을 때 호출한 재귀함수로부터 반환받은 값과, 물건을 넣었을 때 호출한 재귀함수로 부터 반환받은 값에 현재 물건의 절박도를 더한 값 중 최댓값을 반환해주게 된다.

  • cache[capacity][num] : capacity의 용량을 num번부터 n번까지의 물건들로 채울 때 절박도의 최댓값을 저장

  • 함수 탈출 조건 : 현재 넣으려는 물건의 idx번호가 범위를 초과하면 탈출 (obidx==num)

• 넣은 물건의 리스트 구하기

  • 최대 절박도를 구하는 함수를 통해 답을 역추적하여 넣은 물건의 리스트를 구할 수 있다.

  • 현재 물건을 넣었을때의 최대 절박도와 현재 물건을 안넣고 넘어갔을때의 최대 절박도가 같다 -> 현재 물건은 최대절박도에 영향을 미치지 않는다 -> 챙기지 않은 짐

  • 현재 물건을 넣었을때의 최대 절박도와 현재 물건을 안넣고 넘어갔을때의 최대 절박도가 다르다 -> 현재 물건은 최대절박도에 영향을 미친다 -> 챙긴 짐

  • 최대 절박도 구하는 함수에서 물건을 챙길때 리스트를 만들어 보려다가 계속 실패했다. 이렇게 완전탐색에서 원하는 한가지의 경우를 보여줘야하는 문제가 나왔을 때, 새로운 함수를 만들고 그 함수에서 완전탐색을 구현한 함수를 이용해 원하는 과정을 저장할 수 있다는 것을 알았다.

 

 

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