배낭 문제
각기 다른 가치 V를 지닌 N개의 물건이 있을 때, 배낭에 넣을 수 있는 최대 무게 W 이하로 최대 가치를 찾는 것이 정석적인 배낭 문제다.
가능한 모든 조합 2^N개를 확인하여 최대 가치를 확인할 수 있겠지만, N의 최댓값에 따라 시간 초과가 날 가능성이 매우 높아진다.
그래서 다이나믹 프로그래밍 DP 접근이 더 적합한 문제다.
DP로 Knapsack을 풀어보자
1. 소문제 정의
모든 DP 접근은 점화식 도출로부터 시작된다.
배낭에 물건을 넣을 때 선택지는 (1) 물건을 넣거나, (2) 물건을 넣지 않거나 총 2가지다.
가장 큰 구분 조건은 빈 배낭에 들어갈 수 있는지다. 일단 물건의 무게가 배낭의 허용치를 초과하지 않는다면 넣는 시도는 해야 한다.
물론 현재 내가 넣고자 하는 물건의 무게가 배낭의 허용 가능 무게를 초과한다면 이 물건은 아예 고려조차 할 수 없다.
if (weights[i] > W) dp[i][W] = dp[i-1][W]; 위 코드처럼 이전 값을 그대로 가져와서 새로운 물건을 아예 추가하지 않는다.
2. 그럼 이 물건을 넣어야 하나?
일단 배낭 안에 들어갈 수 있는 물건인 건 확인했다. 그러면 최대 가치를 위해서 이 물건을 넣어야 할지 결정해야 한다.
(1) 현재 물건을 넣지 않거나, (2) 현재 물건을 넣을 공간을 만들어서 물건을 넣는 2가지 방법이 있다. 이 중에서 더 큰 값을 선택해서 가치를 최대로 가져갈 수 있다.
dp[i][w] = Math.max(dp[i-1][w], dp[i][w - weights[i]] + values[i]);3. 코드로 구현해보자
표로 DP적 사고를 실현해보자. row는 최대 무게, column은 물건의 번호로 정의한다. i번째 row, j번째 column의 셀은 최대 무게 i를 가정하고 j번째 물건까지 고려했을 때의 최대 가치 값이다.
배낭의 최대 무게가 0이거나 물건이 없으면 가치는 당연히 0이다. 이렇게 0번째 컬럼과 0번째 행을 모두 0으로 채울 수 있다.
int[][] dp = new int[N+1][N+1];
// int 배열은 셀 값이 모두 0으로 초기화되기 때문에 초기화 작업은 생략한다
i번째 row, j번째 컬럼의 셀 값을 채우고자 할 때 다음의 과정을 거칠 수 있다.
- j번째 물건이 최대 무게보다 작거나 같은가?
- 1번을 충족하면, j-1번째 물건을 제거하고 j번째 물건을 넣는게 가치가 더 높은가?
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (현재_물건의_무게 <= j) { // 현재 물건의 무게가 현재 배낭의 최대 무게보다 작은지
if (현재_물건의_가치 + dp[i-1][j-현재_물건의_무게] > dp[i-1][j]) {
dp[i][j] = 현재_물건의_가치 + dp[i-1][w - 현재_물건의_무게];
} else dp[i][j] = dp[i-1][j];
} else dp[i][j] = dp[i-1][j];
}
}
관련 백준 문제
벼락치기 #29704 (골드 5)
평범한 배낭 #12865 (골드 5)
References: https://jeonyeohun.tistory.com/86
