[백준] 12865번 - 평범한 배낭 [Java]

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

 

[백준] 12865번 - 평범한 배낭 [Java]

[백준] 12865번 - 평범한 배낭 [Java]

---

1.  아이디어

 

대표적인 0-1 배낭 문제로 다이나믹 프로그래밍으로 해결할 수 있다.
직관적인 2차원 dp 테이블을 활용한 방식과 좀 더 발전한 1차원 dp 배열을 활용한 방식으로 해결했다.

---

2. 문제풀이

 

2차원 dp 테이블은 행을 물건의 번호, 열을 무게로 하면 되고 1차원 dp 배열은 무게를 인덱스로 하면 된다.

2차원 dp 테이블은 행 번호가 늘어날수록 고려하는 물건의 종류가 늘어난다고 생각하면 되고 현재 번호의 물건을 담았을 때와 안 담았을 때 중 최댓값을 찾으면 된다.
1차원 dp 배열은 2차원 dp 테이블이 이전 행의 정보로 현재 행을 구성하는 점에 착안해 갱신해주면 되고 이때 인덱스를 뒤에서부터 갱신해줘서 같은 물건이 중복으로 담기는 것을 방지해줬다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main_1D {

    private static class Item {
        int W;
        int V;

        public Item(int W, int V) {
            this.W = W;
            this.V = V;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        Item[] items = new Item[1 + N];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int W = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            items[i] = new Item(W, V);
        }

        int[] dp = new int[1 + K];
        for (int i = 1; i <= N; i++) {
            // 배낭의 최대 무게부터 현재 물건의 무게까지만 탐색하면 됨(더 작아지면 어차피 못 담음)
            for (int j = K; j >= items[i].W; j--) {
                dp[j] = Math.max(dp[j], dp[j - items[i].W] + items[i].V);
            }
        }

        System.out.println(dp[K]);
    }
}

import java.io.*;
import java.util.*;

public class Main_2D {

    private static class Item {
        int W;
        int V;

        public Item(int W, int V) {
            this.W = W;
            this.V = V;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        Item[] items = new Item[1 + N];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int W = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            items[i] = new Item(W, V);
        }

        int[][] dp = new int[1 + N][1 + K];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                // 배낭의 무게가 현재 물건의 무게보다 작으면 못 담음
                if (j < items[i].W) dp[i][j] = dp[i - 1][j];

                // 배낭의 무게가 현재 물건의 무게보다 크거나 같으면 현재 물건을 담는 경우와 안 담는 경우를 비교
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - items[i].W] + items[i].V);
            }
        }

        System.out.println(dp[N][K]);
    }
}

---

4. 후기

 

- 1차원 dp

- 2차원 dp