백준 12865 - 평범한 배낭

문제

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

리뷰

동적 계획법을 활용하여 풀 수 있는 정석적인 문제인 배낭 문제이다.

먼저 메모이제이션을 구현하기 위해 dp 란 2차원 배열을 정의하였다.

• 행 : $i$번째 행은 $i$ 번째 고를 물건을 의미한다.
• 열 : $j$번째 열은 $j$ 무게를 의미한다.
  위와 같이 정의하였을 때 아래와 같은 점화식을 산정할 수 있다.
  $P(i,j) \begin{cases} P(i-1,j) \;\; if \;\; w_{i}>j \\ max\{v_{i}+P(i-1, j-w_i), P(i-1,j)\}\;\; else \end{cases}$
  점화식을 풀어서 설명해보면
• $i$번째 고를 물건의 무게가 현재 가능한 무게($j$)를 초과하면
  $i-1$번째 해당 무게($j$)의 경우를 채택한다.
• 그외의 경우 $i$번째 고를 물건의 가치+$i-1$개 물건을 고른 경우중 현재 무게에서
  현재 고를 물건의 무게를 뺀 경우와 $i-1$개 물건을 고른 경우중 현재 무게에
  해당하는 경우의 가치를 비교하여 더 큰 경우를 채택한다.

이중 for 문을 사용하기에 로직의 시간 복잡도는 $O(NK)$가 되고, 최대 연산
횟수인 $100 \times 100,000$의 경우에도 무난히 제한 조건을 통과한다.

코드

import java.util.*;

import static java.lang.Integer.parseInt;

public class Main {
    static int N, K;
    static int[][] dp;
    static Stuff[] stuffs;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(in.nextLine());

        N = parseInt(st.nextToken());
        K = parseInt(st.nextToken());

        dp = new int[N + 1][K + 1];
        stuffs = new Stuff[N + 1];
        for (int i = 1; i < stuffs.length; i++) {
            st = new StringTokenizer(in.nextLine());
            int w = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());

            stuffs[i] = new Stuff(w, v);
        }

        for (int i = 1; i < dp.length; i++)
            for (int j = 1; j < dp[i].length; j++) {
                if (i == 0 || j == 0)
                    continue;

                if (stuffs[i].weight > j)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = Math.max(stuffs[i].value + dp[i - 1][j - stuffs[i].weight], dp[i - 1][j]);
            }

        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++)
            maxValue = Math.max(maxValue, dp[i][K]);

        System.out.println(maxValue);
        in.close();
    }

    static class Stuff {
        int weight, value;

        public Stuff(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }

}

결과