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

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

12865번: 평범한 배낭

 

아주아주 유명한 01 배낭문제다. 알고리즘 수업을 들어본 적이 있다면 아마 유사 문제를 풀어봤을 것이다. 내 풀이도 별로 다를거 없다. 다른 사람들 풀이도 봤는데 똑같았다. 

 

dp 문제니깐 dp 정의를 먼저 하자

 

dp[i][j] = m
: 1~i번째 물건의 조합으로 배낭의 무게가 j일때 가치합이 m

 

사실 이 문제는 dp 정의부터 이해하기 어렵다. 처음이라면 아마 많은 시간을 투자해야 할 것이다. 나도 처음에는 뭔소린가 했다. 암튼 dp를 통해 배낭에 물건을 담는 모든 경우의 수를 구할 수 있다. 

 

dp를 조금만 더 자세하게 살펴보자. 우리가 dp에서 관심있는 부분은 dp[1][0] ~ dp[n][k] 이다. 이게 뭘 뜻하는지 보자. 

 

물건의 개수 = n
허용 배낭 무게 = k  

dp[1][0] ~ dp[1][k] 
-- dp[1][0] : 1번째 물건으로 배낭 무게가 0일때의 가치
-- dp[1][k] : 1번째 물건으로 배낭 무게가 k일때의 가치

dp[5][0] ~ dp[5][k]
-- dp[5][19] : 1~5번째 물건의 조합으로 배낭 무게가 19일때의 가치
-- dp[5][25] : 1~5번째 물건의 조합으로 배낭 무게가 25일때의 가치

dp[n][k] : 1~n번째 물건까지 왔을때 배낭 무게가 k일때의 가치

 

알고리즘의 큰 흐름은 아래와 같다. 

i번째 물건을 배낭에 넣을 수 있나?

1) Yes - 넣을지 말지 결정
2) No - 넣지 말자

 

진짜  큰 그림만 적은거다. 이제 하나씩 차근차근 이해해보자.

 

이 문제의 핵심은 배낭에 물건을 넣는 아이디어다. 배낭에 물건을 넣는 것을 어떻게 표현할 수 있을까? 우선 넣는 경우는 좀 어려우니깐 좀 더 쉬운, 넣지 못하는 경우를 보자. 물건을 넣지 못하면 무게와 가치는 아래와 같이 변함없다.  

 

i 번째 물건을 넣지 못하는 경우, 배낭 무게가 j 일때의 가치

dp[i][j] = dp[i - 1][j]

 

배낭의 무게는 j로 동일하다. 왜냐하면 i번째 물건을 넣지 않았기 때문이다. i-1번째 물건까지 넣었을 때 배낭 무게가 j일때의 가치와 값이 같아야 하므로 그대로 대입해준 것이다. 

 

그러면 i번째 물건을 넣는 경우는? 답부터 보자. 

 

i 번째 물건을 넣는 경우, 배낭 무게가 j 일때의 가치


dp[i][j] = dp[ i - 1 ][ j - weight[i] ] + value[i]

weight[i] : i번째 물건의 무게
value[i] : i번째 물건의 가치

j - weight[i] : i번째 물건을 넣기 전의 배낭 무게
dp[ i - 1 ][ j - weight[i] ] : i번째 물건을 넣기 전 배낭 무게의 가치

 

만약에 i번째 물건을 넣는다면 물건의 무게와 가치를 고려해줘야 한다. 왜냐하면 i번째 물건을 넣으면 배낭의 무게와 가치에 변화가 생기기 때문이다. 따라서 dp[i][j]에 들어가는 값은 i번째 물건을 넣기 전 배낭 무게의 가치에 i번째 물건의 가치를 더해줘야 한다. 이 부분이 정말 많이 헷갈려서 이해하는데 시간이 좀 걸릴 것이다. 한번 잘 생각해 보기를!!

 

인덱스는 항상 0 이상이어야 하므로 아래의 조건이 성립한다. 

 

dp[ i - 1 ][ j - weight[i] ] 에서 2차원 원소 인덱스는 0 이상이다.

j - weight[i] >= 0
j >= weight[i] 

 

따라서 물건을 넣을지 말지 고려해줘야 하는 조건은 ( j >= weight ) 가 된다. 그 외에는 물건을 넣을 수 없으므로 물건을 넣지 않을 때와 수식이 똑같다. 

 

물건을 넣을 수 있는 경우에서 넣는 경우와 넣지 않는 경우 중 최대값을 넣어주면 된다. 이를 그대로 코드로 구현하면 아래와 같다. 

 

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

int w[101];
int v[101];
int dp[101][100001];


int main() {
	int n, k, weight, value;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> weight >> value;
		w[i] = weight;
		v[i] = value;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (j >= w[i]) {
				// 무게 여유 있음 - 넣을지 말지 선택
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
			}
			else {
				// 무게 여유 없음 - 넣을 수 없음
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

	cout << dp[n][k] << endl;

	return 0;
}