[백준 / 골드5] 12865 평범한 배낭 (Java)

문제 보기

사용한 것

• 점화식을 세워 풀이하기 위한 bottom-up

풀이 방법

• 2차원 int 배열 dp 선언 (1차 : 아이템 수, 2차 : 무게)
• 새로운 아이템을 고려하면서 dp 갱신
• dp[i][j] : 새로운 아이템을 넣는 것과 넣지 않는 것 중 큰 값
  • 새로운 아이템의 무게가 w, 가치가 v라면 새로운 아이템을 넣는 경우는 dp[i][j] = dp[i - 1][j - w] + v

코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] infos = new int[n + 1][2];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            infos[i][0] = Integer.parseInt(st.nextToken());
            infos[i][1] = Integer.parseInt(st.nextToken());
        }

        // DP
        int[][] dp = new int[n + 1][k + 1];
        int w, v;
        for (int i = 1; i <= n; i++) {
            w = infos[i][0];
            v = infos[i][1];
            for (int j = 1; j <= k; j++) {
                if (j < w) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - w] + v, dp[i - 1][j]);
                }
            }
        }

        // 출력
        System.out.println(dp[n][k]);
    }
}