[백준] 12865번: 평범한 배낭

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

12865번: 평범한 배낭

 

 

 

이 문제는 유명한 배낭 문제(Knapsack Problem)이다.

• 배낭에 짐을 담을 수 있는 최대 무게(k)가 정해져 있음
• 짐들은 모두 각각의 무게(w)와 가치(v)를 갖고 있음
• 가치합이 최대가 되도록 짐들을 어떻게 담을지 결정하는 문제
• 조합 최적화 문제

배낭 문제는 짐을 쪼갤 수 있는 경우(짐의 무게가 소수)와 쪼갤 수 없는 경우(짐의 무게가 양의 정수)로 나뉜다.

• 분할가능 배낭문제(Fractional Knapsack problem): 짐을 쪼갤 수 있는 경우. 그리디 알고리즘으로 푼다
• 0-1 Knapsack problem: 짐을 쪼갤 수 없는 경우. 동적계획법(DP)으로 푼다

 

이 문제는 짐을 쪼갤 수 없는 경우이므로 DP로 풀어야한다

먼저 각 물건의 무게와 가치를 배열에 저장한다

 

w[5]

0	1	2	3	4
0	6	4	3	5

v[5]

0	1	2	3	4
0	13	8	6	12

 

DP[n+1][k+1]  (n: 물건 번호, k: 배낭의 최대 무게)

n \ k	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1
2
3
4

 

0) 0번째 행은 0으로 초기화해준다

 

---

 

n \ k	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	0	0	0	0	0	13	13
2
3
4

 

1) 첫번째 물건 (n=1)

 k=1~5

 -물건의 무게가 가방의 최대 용량보다 크므로 물건을 담을 수 없다.

 -물건을 담지 않았을 때의 가치(DP[0][1] ~ DP[0][5])를 그대로 적어준다.

 k=6,7

 -물건의 무게 <= 가방의 최대 용량이므로 물건을 담을 수 있다.

 -물건을 담았을 때의 가치는 13, 물건을 담지 않았을 때의 가치는 0이다. 

 -둘 중 큰 값을 적어준다

 

---

 

n \ k	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	0	0	0	0	0	13	13
2	0	0	0	8	8	13	13
3
4

 

2) 두 번째 물건 (n=2)

k=1~3

 -물건의 무게가 가방의 최대 용량보다 크므로 물건을 담을 수 없다.

 -물건을 담지 않았을 때의 가치(DP[1][1] ~ DP[1][3])를 그대로 적어준다.

k=4

 -물건의 무게 <= 가방의 최대 용량. 물건을 담을 수 있다.

 -물건을 담았을 때의 가치는 8, 물건을 담지 않았을 때의 가치는 DP[1][4]=0이다. 

 -둘 중 큰 값을 적어준다

k=5

 -물건의 무게 <= 가방의 최대 용량. 물건을 담을 수 있다.

 -물건을 가방에 넣으면, 가방의 최대 용량이 1이 남는다.

 -이렇게 물건을 넣고도 가방 용량이 남을 때에는, 현재 물건을 담기 전 상황에서 가방의 최대 용량이 1일 경우의 가치도 더해줘야 한다!! 이 값은 앞에서 구했다 (DP[1][1])

 -따라서 물건을 가방에 담는 경우의 가치는 8 + DP[1][1] = 8, 물건을 담지 않았을 때의 가치는 DP[1][5]=0

 -둘 중 큰 값을 적어준다

k=6

 -물건의 무게 <= 가방의 최대 용량. 물건을 담을 수 있다.

 -물건을 가방에 넣으면, 가방의 최대 용량이 2 남으므로 가치 계산할 때 DP[1][2]를 더해주면 된다

 -물건을 가방에 담는 경우의 가치는 8+DP[1][2]=8, 담지 않았을 때의 가치는 DP[1][6]=13

 -둘 중 큰 값을 적어준다

k=7

 -물건의 무게 <= 가방의 최대 용량. 물건을 담을 수 있다.

 -물건을 담는 경우의 가치: 8 + DP[1][3] = 8, 담지 않았을 때의 가치는 DP[1][7]=13

 -둘 중 큰 값을 적어준다.

 

---

 

정리하면,

 

 (1) w[n] > k 인 경우, DP[n][k] = DP[n-1][k]

 (2) w[n]<=k인 경우, DP[n][k] = max( DP[n-1][k-w[n]] + v[n] , DP[n-1][k] )

 

---

 

이 방법으로 배열을 모두 채워준다

n \ k	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	0	0	0	0	0	13	13
2	0	0	0	8	8	13	13
3	0	0	6	8	8	13	14
4	0	0	6	8	12	13	14

 

이 배열에서 가장 큰 값을 출력하면 정답

 

---