[백준] 12865번 평범한 배낭 (자바 풀이)

문제

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

12865번: 평범한 배낭

풀이

이 문제는 배낭 문제(Knapsack)로 유명한 문제이다. 처음 이 문제를 봤을 땐 그리디 알고리즘을 떠올렸다. 하지만 그리디 알고리즘으로는 이 문제를 해결할 수 없다. 

 

배낭 문제는 짐을 쪼갤 수 있는 경우는 Fraction Knapsack Problem이라고 하고 그리디 알고리즘으로 해결할 수 있다.

짐을 쪼갤 수 없는 경우는 0/1 Knapsack Problem이라고 하고 DP를 사용하여 해결할 수 있다. 

 

이 문제는 짐을 쪼갤 수 없으므로 다이나믹 프로그래밍을 사용해서 풀어야한다.

 

예제를 이용해 예시를 들자면 다음과 같다.

 

2차원 배열 dp[][]를 만든다.

dp배열의 의미는 dp[아이템 index][무게] = 가치 이다. 

아래 진행과정을 보면 이해할 수 있을 것이다.

 

itme1은 무게가 6이고 가치가 13이므로 무게가 1~5 일때는 담을 수 없고, 6일때부터 담을 수 있다.

따라서 무게 6에 가치 13을 표시한다(dp[1][6]=13) 또한 무게 7일때도 담을 수 있으므로 13을 표시해놓는다(dp[1][7]=13)

 

item2 부터는 이전 행의 값들을 복사한다. 즉, dp[i][j] = dp[i-1][j]이다. 예를 들어 dp[2][6] = dp[1][6] = 13이다.

이후 item2는 무게가 4, 가치가 8이므로 무게 4,5에 들어가므로 8을 표시해준다. 무게 6부터는 8보다 13이 더 크므로 갱신하지 않는다.

 item3도 마찬가지로 이전 행의 값들을 복사한다. 이후 item3는 무게가 3, 가치가 6이므로 무게 3에 6을 표시한다. 무게 4부터는 이전 행의 값들이 크므로 갱신하지 않는다.

이때 중요한 점화식이 나온다. item3의 무게는 3이므로 무게7일때 4만큼 더 담을 수 있다. 지금까지 dp[][]배열을 통해 무게에 따른 최대 가치를 누적해왔으므로, 이전 행의 무게4 가치를 item3의 가치와 더한 값 14가 13보다 크므로 갱신해준다. 즉, dp[3][7] = Math.max(dp[3][7], dp[3-1][7-3]+6) = Math.max(13, dp[2][4]+6) = Math.max(13,8+6) = 14이다. 

이를 점화식으로 일반화하면 dp[i][j] = Math.max(dp[i][j], dp[i-1][j-w[i]]+v[i]) 이다. 

마지막으로 item4도 이전 행의 값을 복사한다. item4는 무게 5일때 가치가 12이므로 값을 갱신해준다. 무게 1~7일때 다른 item을 넣을 수 없으므로 계산이 종료된다.

 

사실 설명보다 코드를 보면 이해가 더 빠를 수 있다.

코드

import java.io.*;
import java.util.*;
 
public class Baekjoon_12865 {
    static int N,K;
    static int dp[][], w[], v[];
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        
        dp = new int[N+1][K+1];
        w = new int[N+1];    // 무게 저장
        v = new int[N+1];    // 가치 저장
        
        for(int i=0; i<N; i++) {
            w[i]= sc.nextInt();
            v[i] = sc.nextInt();
        }
        
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=K; j++) {
                dp[i][j] = dp[i-1][j];     // 이전 행 결과 복사
                if(j - w[i]>=0) {    // 무게가 남으면
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-w[i]]+v[i]); // 더 큰 값으로 갱신
                }
            }
        }
        
        System.out.println(dp[N][K]);
 
    }
    
}
 

결과