[백준/C++] 12865. 평범한 배낭

문제

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

풀이

처음에는, DP를 어떻게 이용해야할지 떠오르지 않아서 일단 완전탐색으로 구현해보았다. 

결과는 너무 당연하게도 시간초과였다! 

완전탐색으로 구현하고 나면, DP에 대한 감이 올거라고 생각했는데 전혀 오지 않았다. 

 

결국 검색의 힘을 빌렸는데, 이 문제는 대표적인 "냅색 문제"라고 한다.

냅색 문제(knapsack problem)란?

냅색 문제를 알아듣기 쉽게 표현하면, "배낭 채우기 문제"이다. 

즉, 주어진 조건 하에서 최대한으로 배낭을 채우려면 어떻게 해야 하는가? 에 대한 문제이다.

 

풀이법

• 완전탐색
  • 복잡도 : O(N^2) -> 시간초과 가능성
• Greedy 
  • 항상 최적의 답이라는 보장이 없다
• DP
  • 어떤 문제에 DP를 적용하기 위해서는 해당 문제에 최적의 원리가 성립되어야 한다.
    • 최적의 원리? : 어떠한 경우의 최적의 해가, 이 경우를 분할한 부분 사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대해 최적의 원리가 성립한다. 
    • 이 원리를 냅색 문제에 적용하면, 
      • 집합 A : 냅색 문제의 최적의 해에서 가방에 담긴 물건들의 집합
      • 집합 A가 n번째 물건을 포함하지 않는다면, 
        • A는 n번째 보석을 제외한 나머지 n-1개의 물건들 중에 최적으로 고른 부분집합과 같다. 
      • 집합 A가 n번째 물건을 포함한다면,
        • A에 속한 물건들의 총 가격 = n-1개의 물건들 중에서 최적으로 고른 가격의 합 + n번째 물건의 가격 
    • 이것을 점화식으로 풀어쓰면 아래와 같다.
      • P[i, w] : i개의 보석, 가방의 무게 한도 w 일 때 최대의 이익

완전탐색 코드 (시간초과) 

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

using namespace std;

int k,n;
int maxV = 0;
vector<vector<int>> objList;
void func(int start, int wSum, int vSum) {
	for (int i = start;i < n;i++) {
		if (wSum + objList[i][0] > k) {
			maxV = max(maxV, vSum);
			continue;
		}
		func(i, wSum + objList[i][0], vSum + objList[i][1]);
	}
}
int main(void) {
	//n: 물건의 개수, k:가방에 넣을 수 있는 최대 무게 
	cin >> n >> k;

	for (int i = 0;i < n;i++) {
		int w, v;
		cin >> w >> v;
		objList.push_back({ w,v });
	}
	func(0, 0, 0);
	cout << maxV << endl;

	return 0;
}

 

DP 코드 (성공!)

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

using namespace std;

int main(void) {
	//n: 물건의 개수, k:가방에 넣을 수 있는 최대 무게
	int k, n;
	vector<vector<int>> objList;
	
	cin >> n >> k;
	vector<vector<int>> cache(n+1, vector<int> (k+1));
	objList.push_back({0,0});
	for (int i = 0;i < n;i++) {
		int w, v;
		cin >> w >> v;
		objList.push_back({ w,v });
	}
	for (int i = 1;i <= n;i++) {
		for (int j = 0;j <= k;j++) {
			int weight = objList[i][0];
			if (j < weight)
				cache[i][j] = cache[i-1][j];
			else
				cache[i][j] = max(cache[i - 1][j], cache[i - 1][j - weight] + objList[i][1]);

		}
	}
	cout << cache[n][k];
	return 0;
}

 

결과