[백준] 18625 평범한 배낭

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

12865번: 평범한 배낭

 

1. DFS

입력 값 N, K에 대하여,

N은 물품의 수이고, K는 준서가 버틸 수 있는 무게이다.

K 무게를 넣을 수 있고,

입력받은 물건을 차례로 인덱스를 부여할 때, 해당 인덱스부터 탐색하여 가능한 경우를 찾는다.

가능한 경우는 1) 물건을 넣지 않는 경우, 2) 물건을 넣는 경우가 있고,

1) 의 값과 2) + 물건의 가치 값 중 큰 값을 반환한다.

dfs

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

int		dfs(int weight, int idx, vector<pair<int, int> >& tmp, int n){
	int		i, first, value;

	//탐색할 물건이 없는 경우
	//더이상 물건을 넣지 않는 경우
	if (idx == n || weight == 0)
		return 0;
	value = 0;
	//물건을 넣는 경우
	if (tmp[idx].first <= weight){
		first = dfs(weight - tmp[idx].first, idx + 1, tmp, n) + tmp[idx].second;
		value = max(first, value);
	}
	//물건을 넣지 않는 경우
	value = max(value, dfs(weight, idx + 1, tmp, n));
	//최대값 반환
	return value;
}

int		main(){
	int		n, k;
	int		w, v;
	vector<pair<int, int> >	backpack;

	cin >> n >> k;
	for (int i = 0; i < n; i++){
		cin >> w >> v;
		backpack.push_back(pair<int, int>(w, v));
	}
	cout << dfs(k, 0, backpack, n) << endl;
	return 0;
}

 

최악의 경우, 탐색할 인덱스가 0 ~ n 까지 모두 탐색하는 것으로 포화이진트리의 노드 개수는 트리의 깊이가 a 일 때, 2^n - 1 개이다.

따라서, O(2^n)의 시간이 소요된다.

n = 100일 때, 최악의 경우, 2^100번 시행되므로 시간 초과가 발생한다.

 

 

2. DP

위와 같은 방식으로 작성하되, 시간 초과를 막기위해 값들을 한 번 계산한 뒤 결과를 저장한다.

이때, 인덱스가 클수록, 배낭에 넣을 수 있는 무게가 작을 수록, 다른 값을 덜 참조하므로 순서에 따라 계산을 한다!

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

int		dp(int weight, int idx, vector<pair<int, int> >& tmp, int n, vector<vector<int> >& result){
	int		i, first, value;

	value = 0;
	//배낭에 넣는 경우
	if (tmp[idx].first <= weight)
		value = result[weight - tmp[idx].first][idx + 1] + tmp[idx].second;
	//배낭에 넣지 않는 경우
	value = max(value, result[weight][idx + 1]);
	//최대값 반환
	return value;
}

int		main(){
	int		n, k;
	int		w, v;
	vector<pair<int, int> >	backpack;
	vector<vector<int> > result;

	cin >> n >> k;
	for (int i = 0; i < n; i++){
		cin >> w >> v;
		backpack.push_back(pair<int, int>(w, v));
	}
	//값 초기화
	result.assign(k + 1, vector<int>(n + 1, -1));
	//k == 0 인 경우
	for (int i = 0; i <= n; i++)
		result[0][i] = 0;
	//i == n 인 경우
	for (int i = 0; i <= k; i++)
		result[i][n] = 0;
	//result 값 구하기
	for (int j = n - 1; j >= 0; j--){
		for (int i = 1; i <= k; i++)
			result[i][j] = dp(i, j, backpack, n, result);
	}
	//결과 출력
	cout << result[k][0] << endl;
	return 0;
}

소요 시간은 N * K + 2N + K 이므로, O(N * K)이고,

최대 10^2 * 10^5, 약 10^7 번 계산한다.