<BOJ> 12865 자바 (평범한 배낭)

 

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

 

문제 설명

이 문제는 전형적인 배낭 문제(Knapsack Problem)로, 다이나믹 프로그래밍(DP)을 사용하여 해결할 수 있다.

주어진 물품들을 배낭에 넣을 때, 배낭이 담을 수 있는 최대 무게를 초과하지 않으면서 물품들의 가치 합을 최대화하는 문제이다.

 

다이나믹 프로그래밍의 기본 개념

다이나믹 프로그래밍은 복잡한 문제를 작은 부분 문제로 나누어 해결하는 방법이다.

각 부분 문제는 한 번만 풀고, 그 결과를 재사용하여 전체 문제를 해결한다.

이번 배낭 문제가 딱 이런류이다.

 

예로, 최대 적재량이 8kg인 배낭에 여러 물건들(weight[])을 담아 최대 가치를 구하고자 한다.

각각 가치가 3, 4이고, 무게가 3, 4인 1, 2번 물건을 담은 것이, 가치가 2이고 무게가 8인 3번 물건이 있다고 가정해보자.

이 때, 3개의 물건을 담는 동안 1, 2번 물건을 담은게 3번째 물건을 담은 것 보다 가치가 크므로

dp[몇번째 물건][최대 무게]로 보았을 때, dp[3][8] = dp[i-1][8]이 된다.  (dp[i-1][7]==dp[i-1][8])

 

배낭 문제를 다이나믹 프로그래밍으로 해결하는 방법

1. 상태 정의:
   • dp[i][w]는 i번째 물건까지 고려했을 때, 배낭의 최대 무게가 w일 때의 최대 가치이다.
2. 점화식:
   • 물건 i를 배낭에 넣지 않는 경우: dp[i][w] = dp[i-1][w]
   • 물건 i를 배낭에 넣는 경우 (물건 i의 무게가 w 이하일 때): dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
3. 초기 상태:
   • dp[0][w] = 0 (물건이 하나도 없을 때는 가치가 0)

 

풀이 코드

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 W = Integer.parseInt(st.nextToken()); // 최대 무게

        int[] weight = new int[N + 1];
        int[] value = new int[N + 1];

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

        int[][] dp = new int[N+1][W+1];   // dp[0][]은 아무 물건도 넣지 않았을때

        for (int i = 1; i <= N; i++) {
            for (int w = 0; w <= W; w++) {
                if (w >= weight[i]) {
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weight[i]] + value[i]);
                } else dp[i][w] = dp[i - 1][w];
            }
        }
        System.out.println(dp[N][W]);


    }
}