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

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

 

 

 

알고리즘 분류

• 다이나믹 프로그래밍
• 배낭 문제

 

풀이

대표적인 DP 알고리즘을 사용하는 배낭 문제이다.

Bottom-UP 방식을 사용했고 DP의 SubProblem은 물건을 담을 때나 담지 않을 때를 생각했다.

 

예시는 백준에 나와있는 입출력을 기준으로 아래의 표와 함께 설명하겠다.

백준 예시

 

 

• 초기 상태 (행 0): DP 테이블의 첫 번째 행은 물건을 하나도 고려하지 않은 상태이다. 따라서 모든 값이 0으로 초기화되어 있다. 당연히 배낭의 무게가 얼마이든지 물건을 하나도 넣지 않으면 가치는 0이기 때문이다.

물건 \ 무게	0	1	2	3	4	5	6	7
X	0	0	0	0	0	0	0	0

 

• 물건 1 (무게 6, 가치 13) - 행 1:
  • 배낭의 무게가 1부터 5까지는 물건 1의 무게(6)를 담을 수 없기 때문에 모두 0이다.
  • 무게가 6 이상인 경우에는 물건 1을 배낭에 넣을 수 있다. 따라서 무게 6과 7에서의 최대 가치는 13으로 갱신된다.

  물건 \ 무게	0	1	2	3	4	5	6	7
  X	0	0	0	0	0	0	0	0
  물건 1 (w:6, v:13)	0	0	0	0	0	0	13	13

 

 

• 물건 2 (무게 4, 가치 8) - 행 2:
  • 배낭의 무게가 1부터 3까지는 물건 2의 무게(4)를 담을 수 없기 때문에 모두 이전 값인 0을 유지한다.
  • 무게가 4일 때, 물건 2를 넣을 수 있으며 최대 가치는 8로 갱신된다.
  • 무게 5에서도 최대 가치는 8이다. 무게 6에서는 물건 1을 넣는 경우와 비교하여 최대 가치가 13으로 유지된다.
  • 무게 7에서도 물건 1을 넣는 경우가 더 높은 가치를 가지므로 13이 유지된다.

  물건  \ 무게	0	1	2	3	4	5	6	7
  X	0	0	0	0	0	0	0	0
  물건 1 (w:6, v:13)	0	0	0	0	0	0	13	13
  물건 2 (w:4, v:8)	0	0	0	0	8	8	13	13

 

 

• 물건 3 (무게 3, 가치 6) - 행 3:
  • 배낭의 무게가 1과 2에서는 물건 3의 무게(3)를 담을 수 없기 때문에 이전 값인 0을 유지한다.
  • 무게 3에서는 물건 3을 넣을 수 있으며 최대 가치는 6으로 갱신된다.
  • 무게 4에서는 물건 2를 넣은 경우의 가치가 8로 더 크기 때문에 그대로 8을 유지한다.
  • 무게 5에서는 물건 3을 넣는 경우 가치가 6이지만 물건 2를 넣는 경우가 더 크기 때문에 8을 유지한다.
  • 무게 6에서는 물건 1을 넣는 경우가 더 높은 가치를 가지므로 13이 유지된다.
  • 무게 7에서는 물건 2와 물건 3을 함께 넣어 최대 가치가 14로 갱신된다.

  물건  \ 무게	0	1	2	3	4	5	6	7
  X	0	0	0	0	0	0	0	0
  물건 1 (w:6, v:13)	0	0	0	0	0	0	13	13
  물건 2 (w:4, v:8)	0	0	0	0	8	8	13	13
  물건 3 (w:3, v:6)	0	0	0	6	8	8	13	14

 

 

• 물건 4 (무게 5, 가치 12) - 행 4:
  • 배낭의 무게가 1부터 4까지는 물건 4의 무게(5)를 담을 수 없기 때문에 이전 값들을 그대로 유지한다.
  • 무게 5에서는 물건 4를 넣을 수 있으니 최대 가치는 12로 갱신된다.
  • 무게 6에서는 이전 최대 가치인 13이 더 크기 때문에 그대로 유지된다.
  • 무게 7에서는 물건 3을 넣었을 때의 최대 가치인 14가 유지된다.

  물건  \ 무게	0	1	2	3	4	5	6	7
  X	0	0	0	0	0	0	0	0
  물건 1 (w:6, v:13)	0	0	0	0	0	0	13	13
  물건 2 (w:4, v:8)	0	0	0	0	8	8	13	13
  물건 3 (w:3, v:6)	0	0	0	6	8	8	13	14
  물건 4 (w:5, v:12)	0	0	0	6	8	12	13	14

 

최종 결과

배낭의 최대 무게가 7일 때, 물건들을 최적으로 선택하여 넣었을 때 얻을 수 있는 최대 가치는 14이다. 

 

동적 프로그래밍 점화식

이 문제를 해결하기 위해 사용된 점화식은 다음과 같다.

dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i]] + values[i])

즉, i번째 물건을 넣을 수 있는 경우와 넣지 않는 경우 중에서 더 큰 가치를 선택하는 방식이다. 이를 통해 최적의 해를 구할 수 있다.

 

 

 

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    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());

        int [][] dp = new int[N+1][K+1];

        int []W = new int[N+1]; // Weight
        int []V = new int[N+1]; // Value

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

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {

                if(j-W[i] < 0){
                    dp[i][j] = dp[i-1][j];
                    continue;
                }

                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-W[i]] + V[i]);
            } // for
        } // for

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