백준 12865. 평범한 배낭

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

12865번: 평범한 배낭

 

1. 문제 설명

 

n개의 물건이 있고, 각 물건은 무게 w와 가치 v를 가진다.

준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다.

배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구해라

 

2. 접근법

 

해당 문제를 보고 바로 떠오른 알고리즘은 브루트 포스 알고리즘이다

n개의 아이템 각각을 넣을지 말지를 따져서 배낭의 가치가 최대가 될 때를 출력하면된다

하지만, 문제에서 주어지는 n의 범위는 1 <= n <= 100이고 시간 제한이 2초이기 때문에 시간 초과가 뜬다

 

이를 더 효율적으로 처리해야한다

 

문제를 보면 아이템이 배낭에 들어있는 경우와 들어있지 않은 경우로 구분할 수 있으며 배낭의 무게 최대 k 만큼 담을 수 있다

배낭의 무게에 제한이 있기 때문에 해당 문제는 분할이 가능하다

예를 들어서 k = 7이고 아이템이 4개이며 각 아이템의 무게와 가치를 밑에와 같을 때(왼쪽 무게, 오른쪽 가치)

6 13
4 8
3 6
5 12

 k = 7인 배낭의 가치는 총 3가지 경우가 가능하다

- 13 ([6/13])

- 12 ([5/12])

- 14 ([4/8], [3/6])

위의 경우에서 가치가 가장 높은 것은 14이다

무게가 k인 배낭을 총 아이템의 무게 합이 k이내이면 해당 아이템들로 구성이 가능하다

(이는 문제가 하위 문제로 분할 할 수 있음을 알 수 있다)

 

k = 12라고 가정했을 때 해당 배낭의 최대 가치는 "k = 5일 때의 최대 가치" + "k = 7일 때의 최대 가치" 이다

- 26 {([5/12), ([4/8], [3/6])}

 

즉, 문제를 각 하위 문제의 결과 값으로 풀 수 있음을 알 수 있다 

 

결론적으로 이 문제를 브루트 포스 방식보다 효율적으로 풀 수 있는 알고리즘은 DP이다

- i번 아이템을 넣을지 말지 판단한다

- 이때, 허용 가능한 무게 범위에 포함된 경우에만 i번 아이템을 넣을 수 있다

- i번 아이템을 넣는다고 했을 때 문제를 분할한다

- dp[i][j] = dp[i-1][j-item[i].weight] + item[i].value

 

dp 점화식은 밑에와 같다

d[i][j] = 현재 i번 아이템까지 고려한 상황이고 무게는 j일 때의 가치의 최대값을 기록한다

 

 

 

3. 설계

 

(1). 입력값 받아서 세팅하기

- (1). int[][] items

- (2). int[][] d

 

(2). dp 알고리즘 적용

- i번 아이템에 대해서 무게가 j일 때 최대 가치 구하기

- i <- 1~n

- j <- 1~k

- 무게를 j로 고정 시켰을 때, i번 아이템의 무게를 포함할 수 있는지 확인

- 포함할 수 있으면 i번 아이템 담고 하위 문제로 분할시키기

 

(3). 정답 출력

- n번까지 아이템을 모두 고려하며 배낭의 무게가 k일 때의 최대 가치 출력

- d[n][k]

 

4. 코드

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


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[][] items = new int[n+1][2];
        for (int i=1; i<=n; i++) {
            String[] line = br.readLine().split(" ");
            int w = Integer.parseInt(line[0]);
            int v = Integer.parseInt(line[1]);

            items[i][0] = w;
            items[i][1] = v;
        }

        for (int i=1; i<=n; i++) {
            for (int j=1; j<=k; j++) {
                dp[i][j] = dp[i-1][j];

                if (j >= items[i][0]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-items[i][0]] + items[i][1]);
                }
            }
        }

        System.out.println(dp[n][k]);

    }
}