[동적 프로그래밍] 백준 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)가 주어진다.

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

출력

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

-----------------------------------------------------------------------------------------------------------------------------------

처음 문제를 봤을 때는 '이거 그리디 문제인가?' 라고 생각했다. 무게나 가치 중 하나를 줄 세워서 눈 앞에 보이는 최선을 고르면 되는 문제 아닌가 생각했으나, 무게와 가치가 항상 비례할 수는 없었다. 때문에 이전의 선택을 계속 고려해야한다. 때문에 이 문제는 DP 문제라고 판단을 내렸다.

그리고, 이 문제는 무게와 가치 둘 다 고려해야 풀 수 있어 보인다. 둘 다 확인하려면 무조건 이중포문을 사용하게 될텐데.. 이를 재귀로 써서 좀 더 효율적으로 풀어보겠다. 재귀가 왜 더 효율적인지는 마지막에 설명하겠다.

 

입력된 물건의 무게와 가치는 전역변수로 두었다. 재귀 함수의 인자로 넣을 시 함수의 덩치가 커질 것을 염려했기 때문이다.

재귀로 물건을 하나씩 확인할 때, 그 물건을 어떻게 처리할 지는 두가지 선택지가 주어진다.

1. 물건을 선택한 경우.

2. 물건을 선택하지 않는 경우.

 

일단 물건을 선택하려면 선택할 물건의 무게가 들 수 있는 무게를 초과하지 말아야한다는 조건이 있다.

그리고 물건을 선택했다면 재귀함수를 호출해 다음 물건과 자기 물건의 무게를 합한 수를 넘겨준다.

if (w + weight[index] <= K) 
        case1 = value[index] + solution(index + 1, w + weight[index]);    // 선택한 경우

 

물건을 선택하지 않았다면, 재귀함수를 호출해 다음 물건과 자기 물건의 무게를 합하지 않은 수를 넘겨주면 된다.

case2 = solution(index + 1, w); // 물건을 선택하지 않은 경우

 

case1과 case2의 최대값을 메모이제이션에 저장해주면 반복적인 부분의 해를 불필요하게 반복하지 않을 것이다.

모든 물건을 확인했지만 최대무게에 도달하지 못했거나 이미 확인한 부분의 해일 때를 재귀함수 종료조건으로 넣어주었다.

 

위에 적어둔 점화식과 조건을 토대로 만든 내 풀이코드다.

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

using namespace std;

int N, K;  // 물품의 수, 버틸 수 있는 수
vector<pair<int, int>> weightValue;
int memo[101][100001];

int solution(int i, int w) {

	if (i == N) 
		return 0;
	if (memo[i][w] > 0) 
		return memo[i][w];

	int case1 = 0;
	if (w + weightValue[i].first <= K) // 버틸 수 있는 무게를 초과하지 않은 경우. 선택 가능
		case1 = weightValue[i].second + solution(i + 1, w + weightValue[i].first);  // 현재 인덱스의 물건을 선택한 경우

	int case2 = solution(i + 1, w); // 물건을 선택하지 않은 경우

	memo[i][w] = max(case1, case2);

	return memo[i][w];
}
int main()
{
	cin >> N >> K;

	for (int i = 0; i < N; ++i)
	{
		int W, V;
		cin >> W >> V;

		weightValue.push_back(make_pair(W, V));
	}

	cout << solution(0, 0);

	return 0;
}

 

-----------------------------------------------------------------------------------------------------------------------------------

같은 문제를 재귀로 풀었을 때와 이중포문으로 풀었을 때의 디버깅 결과다.

 

재귀로 풀었을 때

이중포문으로 풀었을 때

문제를 해결하는 데에 걸린 시간이 확실히 차이가 난다!