BOJ 12865 - 평범한 배낭

문제

이 문제는 아주 평범한 배낭 문제(0/1 Knapsack)이다.

한 달 후면 국가의 부름을 받게 될 정욱이는, 여행을 떠나기로 했다. 여행을 하기 위해 배낭을 하나 구매했는데, 이 배낭에는 최대 K만큼의 무게만 넣을 수 있다. 정욱이가 여행에 필요하다고 생각하는 N개의 물건이 있는데, 각 물건은 무게 W와 가치 V를 가진다. 정욱이는 여행에서 가치의 합이 최대가 되도록 물건을 고르려 한다. 이때 최대 가치를 구하는 프로그램을 작성하시오.

입력

첫 줄에 물품의 수 N (1 ≤ N ≤ 100)과 준비한 배낭의 용량 K (1 ≤ K ≤ 100,000)가 주어진다.

두 번째 줄부터 N개의 줄에 걸쳐 각 물건의 무게 W (1 ≤ W ≤ 100,000)와 해당 물건의 가치 V (0 ≤ V ≤ 1,000)가 주어진다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제

입력 1

출력 1

풀이

핵심 아이디어: 0/1 Knapsack 문제의 전형적인 DP 풀이다. dp[i][k]를 i번째 물건까지 고려했을 때 무게 제한 k 이하에서 얻을 수 있는 최대 가치로 정의하고 재귀 + 메모이제이션으로 해결한다.

점화식:

물건 i의 무게가 k보다 크면: dp[i][k] = dp[i-1][k] (i번째 물건을 담을 수 없음)
물건 i의 무게가 k 이하이면: dp[i][k] = max(dp[i-1][k], dp[i-1][k - W[i]] + V[i])

풀이 단계:

배열 list[i]에 각 물건의 무게와 가치를 저장한다.
dp[i][k]를 null로 초기화하여 아직 계산하지 않은 상태를 표현한다.
recur(N, K)를 호출해 탑-다운 방식으로 결과를 계산한다.
이미 계산된 값(dp[i][k] != null)이면 메모이제이션된 값을 그대로 반환한다.
i가 0 미만이면 가치 0을 반환한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Day353BOJ12865평범한배낭 {
    static int N, K;
    static int[][] list;
    static Integer[][] dp;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        list = new int[N + 1][2];
        dp = new Integer[N + 1][K + 1];
 
        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
        }
        System.out.println(recur(N, K));
        br.close();
    }
 
    private static int recur(int i, int k) {
        if (i < 1)
            return dp[i][k] = 0;
        if (dp[i][k] == null)
            if (list[i][0] > k)
                dp[i][k] = recur(i - 1, k);
            else
                dp[i][k] = Math.max(
                        recur(i - 1, k),
                        recur(i - 1, k - list[i][0]) + list[i][1]);
        return dp[i][k];
    }
}

복잡도

시간: O(NW) — N은 물건 수, W는 배낭 용량. 각 부분 문제 dp[i][k]가 최대 N×W개
공간: O(NW) — DP 테이블 크기

문제