성장기록지
냅색에 대한 정리와 문제풀이-12865 평범한 배낭 본문
Knapsack Problem이란?
그림과 같이 무게 제한이 있는 가방에
넣을 수 있는 최대 가치를 구하는 방법이다.
예를들어 다음과 같이 조건이 주어졌다고 하자.
이 조건에서 최대 가치를 구할 수 있는 방법은 무엇이 있을까?
가장 먼저 완전 탐색이 생각날 것이다. (모든 알고리즘의 기본이기 때문)
각각의 물건이 가방에 담길때와 아닐때를 생각하여서 모든 경우의 수를 탐색하여보면
최댓값을 찾을 수 있을것이다.
하지만 이렇게 탐색을 하게되면 시간복잡도가 무지막지하게 커지게 된다.
물건이 담길지 아닐지에 대한 경우의 수 는 2이다.
그런데 모든 물건에 대하여 다 생각을 해야 하므로 2*2*2*......하여서
2의 n승 (n은 물건의 개수)이 될 것이다. O(2^n)
이렇게되면 매우 비효율적인 방식이 되므로,
머리가 좋은 과거의 척척석박사들은 Knapsack 알고리즘을 만들게 된다.
Knapsack 알고리즘
Dynamic Programing을 활용하여 구현할 수 있다.
먼저 가방에 물건을 넣었을 때와, 넣지 않을때를 구분하여 보자.
NS("ABCD",5)는 ABCD를 아직 넣거나 넣지 않을 수 있고, 가방의 남은 중량이 5라는 뜻이다.
이 때 왼쪽노드처럼 D를 넣었다고 생각하여 D의 가치인 10을 추가해주고, 가방의 남은 중량을 줄일 수 있다.
아니면 오른쪽노드처럼 D를 넣지 않았다고 생각하여 가치와 중량의 변화를 없이 진행할 수 있다.
이러한 과정을 반복하며 각 조건마다의 결과들을 저장해 줄 수 있다.
NS("AB",-2)는 중량이 초과하였으므로 가지치기를 해줄 수 있다.
그렇다면 이러한 점화식이 완성될 것이다.
NS(n,w)는 최대의 Value값을 나타내는 함수이다.
이 함수는,
NS( n - 1 , w - w[n] ) + value[n] <- 물건을 가방에 넣었을 때
NS( n - 1 , w ) <- 물건을 가방에 넣지 않았을 때
이 두가지의 함수 중 큰 값을 넣게 되는 과정을 반복하여
가방의 최대 Value를 구할 수 있을것이다.
그렇다면 이 함수를 토대로 어떻게 다이나믹 테이블을 만들 수 있을까?
아래는 DP값을 저장할 2차원 배열을 구현한 것이다.
Column 항목은 위의 함수에서 n을 의미하는 것이다.
A부터 D까지 1~4번을 부여하여서,
n이 1일 때는 A가 가방안에 있을때와 없을때를 고려하고,
n이 2일 때는 n이 1일 때의 조건에 더해서 B가 가방안에 있을때와 없을때를 고려하겠다는 의미이다.
Row 항목은 가방의 무게(w)이다.
가방의 전체 무게 조건에 따라 저장되는 값이 달라질 것이다.
Q. 왜 1행과 1열들의 값은 다 0으로 되어있나요?
A. 가방에 아무것도 없을때와, 가방의 제한 무게가 0일때는 0일 수 밖에 없기 때문입니다.
우리의 목표는 DP[4][5]의 값을 구하는 것이다.
(모든 물건들을 고려해보고,가방의 무게가 5일때의 가치의 최대값을 구해야 하기 때문에)
바텀업 방식으로 원하는 값을 구해보도록 하겠다.
DP[1][1]을 구한다고 가정해보겠다.
DP[1][1]을 구하려면 DP[n - 1][w - w[n]] + value[n] 과 DP[n - 1][w] 중 큰 값을 가져와야 한다.
( W[n] = n의 무게, value[n] = n의 무게 이다. n=1,2,3,4는 A,B,C,D를 의미.
그렇다면DP[0][0] +30(value[1]을 의미)와
DP[0][1] 중 큰 값을 가져와야 하므로,
DP[1][1]은 30이 된다.
같은 방식으로 배열을 채우면 아래의 그림과 같이 만들 수 있다.
그렇다면 계속 이어나가며 채워보겠다.
DP[2][3]을 생각해보자. value[2]인 B의 가치는20, w[2]인 B의 무게는 2 이다.
그렇다면 max ( DP[2][1] + 20 , DP[2][3] ) 이 되므로 50과 30을 비교하여 50이 저장되어진다.
(아까 말했듯이 DP[n - 1][w - w[n]] + value[n] 과 DP[n - 1][w] 중 큰 값을 가져와야 한다.)
위와 같은 방식으로 표를 모두 채워보았다.
이렇게 DP[4][5]를 구할 수 있게 되었고,
값은 A와 C를 넣어서 70이 된다.
냅색의 시간복잡도
위의 2차원 배열에 한번씩만 방문하여 최댓값을 저장하면 되므로
물건의 개수(n)과 무게의 제한(w)를 곱한 O(n*m)이 된다.
문제풀이 - 12865 평범한 배낭
import sys
input=sys.stdin.readline
N, K = map(int, input().split())
stuff = [[0,0]]
#column는 0~K (배낭 무게) , row는 O~N (물품 개수)
knapsack = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
#물품별 무게,가치
for _ in range(N):
stuff.append(list(map(int, input().split())))
#냅색 문제 풀이
for i in range(1, N + 1):
for j in range(1, K + 1):
# 설명의 W[n]을 의미
weight = stuff[i][0]
# 설명의 value[n]을 의미
value = stuff[i][1]
# j가 weight보다 작으면 물건을 넣지 않은 값을 무조건 가져옴
# 그렇지않으면 j-weight가 음수가 되어버린다.
if j < weight:
knapsack[i][j] = knapsack[i - 1][j]
# 물건을 넣었을 때와 넣지 않았을 때 중 가치가 큰 값을 가져옴
else:
knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])
# 가방의 최대 가치 출력
print(knapsack[N][K])
위의 설명을 기반으로 코드를 구성하였다.
조금 유의해야할 코드를 짚고 가겠다.
# j가 weight보다 작으면 물건을 넣지 않은 값을 무조건 가져옴
# 그렇지않으면 j-weight가 음수가 되어버린다.
if j < weight:
knapsack[i][j] = knapsack[i - 1][j]이 코드는 지금 가방의 무게(j) 보다 물건의 무게 (weight)가 클 때를 의미한다.
이 코드를 이렇게 예외처리를 해주지 않고
value + knapsack[ i - 1 ][ j - weight ] 를 실행한다면 ( 물건을 배낭에 넣을 때를 의미)
j-weight가 음수가 나온다. (배낭이 무게가 초과된다.)
그리하여 코드와 같은 예외처리를 해준것이다.
'알고리즘 > 다이나믹 프로그래밍' 카테고리의 다른 글
| 백준) 9465번 스티커 문제풀이 회고 (0) | 2024.03.14 |
|---|
