[B]BOJ12865 knapsack, dp 뿌수기
https://www.acmicpc.net/problem/12865
배낭에 넣을 수 있는 물건들의 가치의 최댓값
Brute Force
물건 하나 당 가져간다(True) / 안 가져간다(False)를 마킹하는 식으로
배낭에 담을 물건을 정할 수 있음.
T/F 2가지 경우가 있고
물건이 N개, 문제에서는 최대 100개 이므로
2^100 개의 경우의 수에 대해
Case 하나 하나에 대해 ( T F T T F.....T ) 무게와 가치를 계산해야한다.
2^100( Case의 수 ) * 100( N=100 이므로)
시/공간적으로 실현할 수 없다.
Greedy
DP
dp table에는 최대 가치 값을 담을 것이다.
dp table을 이용하여
선택된 dp table의 element를, 가치값을 구하기 위하여
이전에 계산된 값을 참조할 것이고, 다시 계산하지 않을 것이다.
dp_table의 목적
가방 안의 숫자들을 물품의 id라고 가정한다.
1 2 3 에서 4의 물품을 넣었을 때, 무게가 초과한다면
처음부터 계산하지 않고
1 2 3에 계산된 값을 사용하여
다시 물품을 넣기 시작할 것이다.
1 2 3 5 에서 6번 물품을 넣었을 때, 무게가 초과한다면
처음부터 계산하지 않고
1 2 3 5에 계산된 값을 사용하여
다시 7번 물품을 넣기 시작할 것이다.
가방 그림에는 여러 물품이 element로서 들어간 것처럼 보이지만
dp_table에는 여러 물품들의 value의 합산 값 하나만 들어간다.
dp_table 설계
dp 자료구조를 설계하기 위해서는
각 index가 무엇을 의미하는지,
자료구조의 element가 무엇에 의해 결정되는지 파악해야한다.
4개정도 꼽아 볼 수 있다.
w=weight, v=value, n=물건 개수 , k=소지 가능 무게
처음에는 1차원 dp 배열을 생각했으나
배낭에 다음 물건을 담을 때,
하나를 건너 뛰고 담을 수도 있다.
예를 들어, k무게 조건에 의해
3번 물건을 배낭에서 다시 꺼낸 뒤
다음 물건을 넣을 때
4번 물건, 5번 물건, 6번 물건 중 하나를 넣을 수 있다.
2차원 dp 배열로 접근하기로 했다.
마찬가지로 가치 값을 담을 것이고
크기는 N x K이다.
처음에는 왜 최대 무게 k를 열 크기로 설정하는지 이해가 되지 않았다.
물건의 최소 무게가 1이므로 k로 설정한 것이다.
이제 dp 관계식을 세워야한다.
관계식 설계
1. 관계식을 세우기 위해서는 위에서 설계한 dp_table[n][k]의 의미를 알아야한다.
dp_table[n][k]가 의미하는 바는
k이하의 무게를 가진 가방 안에 n개의 물품이 들어있을 때의 최대 가치 값이며
n, k 인덱스는 상태를 알려준다.
어떤 물품이 어떤 순서로 들어있는 지는 중요하지 않다.
물건이 중복되지 않으며, 한 번 넣은 물건은 가방에 있기 때문이다.
2. 그렇다면 dp_table[n][k]는 이전 값으로부터 유도될 수 있는지 경우의 수를 살펴보자.
이 경우의 수는 가방에 물건을 넣음으로서 갱신한다.
dp_table[n][k]의 상태는 앞서 말했듯이,
- 가방의 무게가 k이하인 상태
- n개의 물품이 들어있는 상태
이다.
이 상태는 다음과 같은 상태들로부터 유도될 수 있다.
2.1 가방의 무게가 k이하이고, n-1개 물품이 들어있는 상태
-> n-1개 물품이 들어있어도
총 무게 k이하를 충족할 수 있는 물건들의 총 가치.
추가할만한 물건이 없으면 이 가치값 그대로 넘어올 수 있음.
dp_table[n-1][k]
2.2 가방의 무게가 k -w 이하이고 n-1개 물품이 들어있는 상태
-> n-1개 물품이 들어있지만
무게가 k에 못 미치는 상태로
물건 하나(items[n])를 추가함으로서 dp_table[n][k]가 될 수 있음.
dp_table[n-1][k -w] + v
w = items[n][0]
v = items[n][1]
위 경우의 수로부터 다음 관계식을 유도할 수 있다.
w = items[n][0]
v = items[n][1]
dp_table[n][k] = max(dp_table[n-1][k], dp_table[n-1][k -w ] + v)
초기값 구하기
table의 1행 1열을 쉽게 갱신할 수 있다.
0으로 전부 초기화.
dp_table 갱신 순서
좌측부터 ->
갱신되지 않은 값을 먼저 참조하지만 않으면 된다.
댓글
댓글 쓰기