knapsack(배낭) 알고리즘 - 백준 12865(DP)

정의

: 배낭에 채울 수 있는 용량이 정해져 있을 때, 물건들을 담아 가장 높은 값을 얻는 케이스를 구해야 한다.

 

관련 문제

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

12865번: 평범한 배낭

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

7579번: 앱

 

풀이과정

1. 완전탐색으로 풀어보려고 했으나, 최대 O(2^N)의 시간복잡도가 발생
2. 힙을 이용해 무게가 낮고, 가치가 높은 순으로 정렬하여 정렬한 순으로 선택하여 그리디하게 풀어보려고 했으나 만족하지 않는 경우가 생김
3. Dynamic Programming 사용!

 

DP의 원리

어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대한 최적의 원리가 성립한다.

물품이 n개가 있고, 물품의 가치는 각각 다르다. 가방의 용량은 k일 때 용량의 한도 내에서 얻을 수 있는 가장 높은 가치?

• 집합 A가 n개의 물품을 최적으로 고른 부분 집합이라고 가정
• 집합 A가 n번째 물품을 포함하지 않는다면, A는 n번째 물품을 뺀 나머지 물품 중에 최적으로 고른 부분집합
• 집합 A가 n번째 물품을 포함하고 있다면 A는 n번째 물품을 제외한 n-1개의 물품 중에 최적으로 고른 부분집합 + n번째 물품의 가치를 합한 것과 같다.

A[i][w] = {
	A[i-1][w] (i번째 물품이 배낭의 무게한도 w보다 클 때),
    	max(A[i-1][w], wi) (i번째 물품과 배낭의 무게한도가 같을 때)
	max(v + A[i-1][w-wi], A[i-1][w]) (i번째 물품이 배낭의 무게한도 w보다 작을 때)
    }

• 즉, i번째 물품이 배낭의 무게한도 w보다 크면 i번째 물품을 담을 수 없으므로 이전 값 중 같은 무게한도일 때의 값을 가져온다.
• 그리고 i번째 물품이 배낭의 무게한도 w와 같으면, 이전 값과 현재 물품 중 큰 것이 A[i][w]가 된다.
• i번째 물품이 배낭의 무게한도 w보다 작을 때는 (무게한도 - i번째 물품 무게) 만큼 담았을 때의 최적값과 i번째 물품의 가치를 더한 값, 그리고 이전의 w 한도의 최적값 중 큰 값이 A[i][w]가 된다.

DP라는 2차원 리스트를 만들어 채워나가면서, 앞에서 계산했던 다른 칸의 값을 이용하여 현재 값을 계산한다.

 

12865번 소스

import sys
si = sys.stdin.readline

n, k = map(int, si().split())

things = [0]
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
for _ in range(n):
	w, v = map(int, si().split())
	things.append((w,v))

for i in range(1, n+1):
	w, v = things[i]
	for j in range(1, k+1):
		if j < w:
			dp[i][j] = dp[i-1][j]
		elif j == w:
			dp[i][j] = max(dp[i-1][j], v)
		else:
			dp[i][j] = max(dp[i-1][j], v + dp[i-1][j-w])

print(dp[-1][-1])

• dp라는 2차원 리스트를 (k+1)*(n+1) 크기만큼 선언한다.(+1은 0번 인덱스를 처리하기 위해)
• 2중 for문을 돌리면서 값을 채워 나간다.
• i는 물품의 인덱스, j는 현재 무게 한도이다.
• 따라서 i는 물품의 개수만큼, j는 최대 무게 한도만큼 돌린다.
• w는 i번 인덱스 물품의 무게, v는 가치이다.
• 따라서 현재 무게 한도 보다 물품의 무게가 크면 이전 값으로 채운다.
• 현재 무게 한도 = 물품의 무게 이면 이전 값과 현재 물품의 무게 중 큰 값으로 채운다.
• 현재 무게 한도 > 물품의 무게 이면 이전 값과 현재 물품의 무게 + 이전 값 중 (무게한도 - 현재 물품의 무게)일 때의 값 둘 중에 큰 값으로 채운다.
• 그리고 가장 마지막 값을 출력하면 정답이 출력된다.

 

 

 

 

---

 

참고

https://gsmesie692.tistory.com/113

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)