[백준] 12865 평범한 배낭

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

12865번: 평범한 배낭

 

---

다이나믹 프로그래밍을 공부했다면 한 번쯤 풀어 봤을 배낭 문제입니다.

 

사실 배낭 문제는 두 가지 유형으로 나눌 수 있습니다. 하나는 배낭에 들어갈 물건을 나눌 수 있는 '분할 가능 배낭 문제' 이고, 다른 하나는 물건을 나눌 수 없는 '0-1 배낭 문제' 입니다. 위 문제는 0-1 배낭 문제에 해당하며, 분할 가능 배낭 문제와 관련한 문제는 나중에 다루도록 하겠습니다.

 

이 문제를 풀기 위해서는 DP를 사용한다고 말씀드렸고, DP 풀이 방식에는 타뷸레이션과 메모이제이션이 있는데, 이 문제는 타뷸레이션이 이해가 편하기 때문에 타뷸레이션으로 풀이하겠습니다.

 

테이블을 그리기 위해서는 기준이 있어야 합니다. 여기서 그 기준은 물품의 개수와 배낭에 들어있는 짐의 무게가 될 것 입니다. 

 

다시 말하자면, 배낭에 짐이 1개가 있고, 그 무게가 1일 때 최대 가치, 2 일때 최대 가치, ... K 일때의 최대 가치를 표에 나타내는 것 입니다.  세로 축이 물품의 수, 가로 축이 배낭의 무게를 나타냅니다.

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

 

- 물품의 수가 0인 경우, 모든 가치가 0 입니다. 물품을 배낭에 넣지 않았기 때문입니다.

 

- 물품의 수가 1인 경우, 배낭의 무게가 3인 경우 가치가 6, 무게가 4인경우 가치가 8, ... , 7인 경우 가치가 13 입니다. 여기서 14가 아닌 이유는 물품이 단 한개만 들어가 있는 경우이기 때문입니다.

 

- 물품의 수가 2인 경우, 배낭의 무게가 3인 경우 가치가 6, 무게가 4인경우 가치가 8, ... , 7인 경우 가치가 14 입니다.

여기서는 13이 아닌 14가 되었습니다. 이제 물품을 2개 넣을 수 있기 때문입니다.

 

마지막 5행 8열에는 우리가 배낭에 넣을 수 있는 물품의 최대 가치 합이 저장 되었습니다.

 

 

Python

Java