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

# 문제링크

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

오랜만에 게시글이다.. 요즘 오전 9시부터 저녁 9~10시까지 공부하느라 정신이 없다 ㅠㅠ

 

DP를 더 공부해보려고 찾은 문제이다. 배낭 문제를 풀면서 DP에 감을 잡은 것 같다. 배낭 문제는 유명한 문제더라! 

 

평소 자주 참고하는 얍문님의 블로그를 보고 공부했다. 설명 천재이신거 같다. 

 

DP 의 포인트는 완전 탐색 중에 제일 좋은 케이스만 가지고 발전을 시키는 것이다. DFS나 BFS로 완전 탐색을 하면, 넣었을 때의 경우와 안넣었을 때의 모든 경우를 다 해보고 제일 좋은 케이스를 찾는다. 반면 DP에서는 넣었을 때와 안넣었을 때 중 더 좋은 케이스만 가지고 발전시킨다. 따라서 넣었을 경우와 안넣었을 경우를 비교해서 큰 값만 배열에 넣는것을 반복하면 원하는 값을 얻을 수 있는 로직이다. 

 

평범한 배낭 문제의 경우 물품의 수 범위 N(1 ≤ N ≤ 100), 물품 무게 K(1 ≤ K ≤ 100,000)이다. 완전 탐색으로 저 물품을 넣었을 때 뺐을 때 각각의 경우를 모두 구하는 건 불가능으로 보인다. 완전 탐색의 경우 N이 13 정도 ?? 이상되면 런타임에러가 뜬다. DP 로 푸니 재미있고 뿌듯하긴 한데 다른 문제에 적용할 수 있을지 모르겠다. 몇 개 더 풀어봐야겠다..

 

# 제출 코드 

 

#include <cstdio>
#include <algorithm>
#define MAXN 100

using namespace std;

int N, K;
int Weight[MAXN + 10];
int Value[MAXN + 10];
int DP[MAXN + 10][100000 + 10];

void Input() {
	scanf("%d %d", &N, &K);
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &Weight[i], &Value[i]);
	}
}
int Do_Dynamic() {
	for (int i = 1; i <= N; i++){ // i 번째 물건 
		for (int j = 1; j <= K; j++) { // 가방에 넣을 수 있는 최대 무게가 j 일때 
			// 안넣었을 때랑 넣었을 때 value 비교해서 큰 값으로!
			if (j >= Weight[i]) DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - Weight[i]] + Value[i]);
			else DP[i][j] = DP[i - 1][j]; // 가방에 넣을 수 잇는 최대 무게보다 무거우면 못넣지
		}
	}
	return DP[N][K];
}
int main() {
	Input();
	printf("%d\n", Do_Dynamic());
}