[Week 2] PACKING self review - Queue-ri

[Queue-ri]

PACKING self review

• 파일명: PQR/PACKING/Queue-ri.cpp
• 수행시간: 24ms

1. 고민 과정

테이블 정의와 DP 경로 탐색을 위한 기록을 어떻게 남길지를 고민했고, 그 외엔 딱히 없었습니다.

2. 풀이 아이디어

구하고자 하는 값의 기준은 최대 절박도가 되는 DP 경로이므로 재귀함수의 반환값은 절박도의 합으로 설정합니다.

따라서 테이블에 들어가는 값은 절박도의 합이고, 행과 열은 남은 문제 조건을 적절히 조합하여 물건 번호, 배낭 용량으로 구성합니다.

DP 경로는 물건 번호만 기록해서 인덱스로 접근하도록 했습니다.

3. 작성한 코드와 설명

Advanced-Algorithm-Study/PQR/PACKING/Queue-ri.cpp

Lines 12 to 20 in a5d7dc8

	int pack(int i, int capacity) {
	if (i > N) return 0;
	int &cache = memo[i][capacity];
	if (~cache) return cache;
	if (item_w[i] <= capacity)
	cache = pack(i + 1, capacity - item_w[i]) + want[i];
	return cache = max(cache, pack(i + 1, capacity));
	}

물건 번호가 N보다 크다면 탐색을 종료하고 절박도 0을 반환합니다.

점화식은 물건을 담았을 때와 안 담았을 때의 절박도를 비교해서 큰 쪽을 선택합니다.

Advanced-Algorithm-Study/PQR/PACKING/Queue-ri.cpp

Lines 22 to 32 in a5d7dc8

	int count(int capacity, vector<int> &packed) {
	int sum = 0;
	rep(i, 1, N + 1) {
	if (pack(i, capacity) != pack(i+1, capacity)) {
	sum += 1;
	capacity -= item_w[i];
	packed.push_back(i);
	}
	}
	return sum;
	}

count()는 pack()이 끝난 후 DP 경로를 찾기 위해 수행되는 함수입니다.

재귀함수가 아닌 반복문으로 구현했으며, 매 반복마다 i번째 물건을 담았는지 절박도 값으로 판단합니다.

물건을 담았다면 해당 물건의 인덱스를 vector에 담고, 정답으로 출력할 물건 개수에 +1을 합니다.

Advanced-Algorithm-Study/PQR/PACKING/Queue-ri.cpp

Lines 34 to 44 in a5d7dc8

	int main() {
	int TC; cin >> TC;
	while (TC--) {
	cin >> N >> W;
	rep(i, 1, N+1) cin >> item[i] >> item_w[i] >> want[i];
	memset(memo, -1, sizeof(memo));
	vector<int> packed;
	cout << pack(1, W) << ' ' << count(W, packed) << endl;
	for (auto i : packed) puts(item[i]);
	}
	}

main에선 테이블을 -1로 초기화해줍니다.

puts와의 혼용 때문에 입출력 sync는 끊지 않았습니다.