12865번: 평범한 배낭

문제 설명

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

[문제]

 이 문제는 아주 평범한 배낭에 관한 문제이다.

 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

 

[입력]

 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

 

[출력]

 한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

 

[예제 입력 1]

4 7
6 13
4 8
3 6
5 12

[예제 출력 1]

14

---

풀이

  사실 아직도 해당 캐시 배열의 정확한 의미를 파악 못한 문제이다. 다만 이러한 문제 자체가 배낭 문제(Knapsack Problem)라는 이름으로 유명한 문제라고 한다.

 단순히 완전 탐색으로 해결 방법을 생각해본다면, 버틸 수 있는 만큼의 무게에 맞게 모든 조합의 물품들을 넣으며 그 때의 총 가치를 비교하면 되는 문제이다. 그러기 때문에 주어진 물품들의 무게와 가치를 담은 하나의 배열을 만들고, 그 이후 반복문과 재귀 호출을 통해 모든 경우의 수를 조사해 가장 많은 가치를 반환하면 된다.

하지만 이런 문제가 대개 그렇듯, 경우의 수가 매우 많아 동적 프로그래밍을 통해 계산의 횟수를 줄여야 한다. 대부분의 동적 프로그래밍의 경우에서는 재귀 호출을 반복할 때 증가하거나 감소하는 특정 파라미터를 배열의 인덱스 삼아 캐시 배열을 생성해낸다. 이 문제에선 재귀 호출을 통해 넘기는 파라미터들 중 어떠한 물건을 담을 지 결정하는 index와 현재 가방에 담긴 무게를 나타내는 totalWeight 두 파라미터가 재귀 호출을 계산하는데 중요하기 때문에, 이 2가지를 인덱스 삼은 이차원 캐시 배열을 생성해내고, 계산을 진행하며 값을 저장하고 반환하거나 해당 캐시 값을 반환하는 것으로 계산의 횟수를 줄여 문제를 푸는 데 성공하였다.

 물론 단순히 캐시 배열이 가지는 의미는 현재 가방의 무게가 K인 상황에서 N번째 물품을 넣을 때의 계산 결과가 존재하는 지 조회하는 것이지만, 이를 문제 풀이 과정에서 이해하기에는 너무나 어려웠다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> cache;//캐시 배열
//완전 탐색 코드
int search(vector<pair<int, int>> &goods, int N, int K, int index, int totalWeight) {
	int result = 0;
	
	if (totalWeight >= K)//현재 총 무게 >= 버틸 수 있는 무게
		return 0;

	if (index == N)//끝에 도달
		return 0;

	if (goods[index].first + totalWeight > K)//현재 담을 물품의 무게와 총 무게의 합 > K
		return 0;

	if (cache[index][totalWeight] != -1)//캐시 값 반환
		return cache[index][totalWeight];

	for (int i = index + 1; i < N; i++) {//기본적인 완전 탐색
		result = max(result, search(goods, N, K, i, totalWeight + goods[index].first));
	}

	return cache[index][totalWeight] = goods[index].second + result;//캐시 저장 후 반환
}

int main()
{
	int N, K;
	vector<pair<int, int>> goods; //무게, 가치
	int tmp1, tmp2;
	int answer = 0;

	cin >> N >> K;

	for (int i = 0; i < N; i++) {//무게와 가치를 담을 배열과 캐시 배열 초기화
		cin >> tmp1 >> tmp2;
		goods.push_back(make_pair(tmp1, tmp2));

		vector<int> temp(K, -1);
		cache.push_back(temp);
	}

	for (int i = 0; i < N; i++) {//탐색
		answer = max(answer, search(goods, N, K, i, 0));
	}

	cout << answer << endl;

	return 0;
}

---

결과