[Algorithm] 12865 - 평범한 배낭

목차

---

1. 문제 설명

2. 정답

 

 

 

 

 

1. 문제 설명

---

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

 

 

 

정말 말그대로 평범한 배낭 알고리즘 문제로, 점화식을 도출하는 방법을 정리해보려고 한다.

배낭 알고리즘은 전형적인 dp문제다. 

결국에 배낭에 물건을 담냐, 담지 않느냐로 쪼갤 수 있기 때문이다.

 

 

 

예시

 

 

먼저 dp 배열을 정의해보자.

 

dp[i][w]

• i번째까지의 물건을 고려했을 때
• 무게 w를 버틸 수 있는 배낭의 최대 가치

 

물건을 선택할 때에는 두 가지 선택지가 있다.

 

1. 현재 물건의 무게가 배낭에 담을 수 있는 최대 무게를 초과

 

첫 번째 물건의 무게는 8kg로 배낭에 최대로 담을 수 있는 무게인 7kg를 초과한다.

이 경우, 배낭에 물건을 담을 수 없다.

따라서 이전 상태의 값을 그대로 가져온다.

 

점화식은 아래와 같다.

dp[i][w] = dp[i - 1][w]

 

 

2. 현재 물건의 무게가 배낭에 담을 수 있는 최대 무게 이하

 

두 번째 물건의 무게는 4kg로 배낭에 최대로 담을 수 있는 무게인 7kg 이하다.

 

이 경우, 다시 두 가지 선택지가 있다.

① 배낭에 물건을 담지 않는다.

② 배낭에 물건을 담는다.

 

따라서 두 가지 경우에 대한 결과를 각각 구하고 더 큰 값을 취하면 된다.

---

① 배낭에 물건을 담지 않는다.

배낭에 물건을 담지 않는 경우는 1번과 동일하다.

 

dp[i][w] = dp[i - 1][w]

---

 

② 배낭에 물건을 담는다.

배낭에 최대로 담을 수 있는 무게는 7kg로 정해져있다.

현재 물건(4kg, 가치 8)을 무조건 배낭에 넣었을 때 최대 가치는 현재 물건의 가치 + dp[0][7kg - 4kg]와 같다.

 

이를 점화식으로 표현하면

dp[i][w] = i번째 물건의 가치 + dp[i - 1][w - (i번째 물건의 무게)] 이다.

---

배낭에 물건을 담지 않는 경우, 배낭에 물건을 담는 경우에 대한 결과를 각각 구했다면 이제 둘 중 더 큰 값을 할당해주면 된다. 현재 물건의 무게가 배낭에 담을 수 있는 최대 무게 이하인 경우 최종 점화식은 다음과 같다.

 

dp[i][w] = Math.max(dp[i][w] = dp[i - 1][w], i번째 물건의 가치 + dp[i - 1][w - (i번째 물건의 무게)])

 

 

.

.

.

 

💡 마지막으로 최종 정리하자면 💡

 

1. 현재 물건의 무게가 배낭에 담을 수 있는 최대 무게 초과

dp[i][w] = dp[i - 1][w]

 

 

2. 현재 물건의 무게가 배낭에 담을 수 있는 최대 무게 이하

dp[i][w] = Math.max(dp[i][w] = dp[i - 1][w], i번째 물건의 가치 + dp[i - 1][w - (i번째 물건의 무게)])

 

 

 

 

2. 정답

---

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));
        String[] input = br.readLine().split(" ");

        int N = Integer.parseInt(input[0]); // 물건의 개수
        int K = Integer.parseInt(input[1]); // 준서가 버틸 수 있는 무게
        int[][] item = new int[N][2]; // 물건 정보
        int[][] dp = new int[N][K + 1]; // 가방의 최대 무게가 K, 인덱스 N번까지 봤을 때의 최대 가치

        for(int i = 0; i < N; i++) {
            String[] info = br.readLine().split(" ");
            item[i][0] = Integer.parseInt(info[0]); // 물건의 무게
            item[i][1] = Integer.parseInt(info[1]); // 물건의 가치
        }

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < K + 1; j++) {
                // 1. 물건이 가방 무게 초과 (담지 않음)
                if(item[i][0] > j) {
                    dp[i][j] = (i == 0) ? 0 : dp[i-1][j];
                }

                // 2. 물건이 가방 무게 이하
                if(item[i][0] <= j) {
                    // 담는다, 담지 않는다 2가지 선택지 가능 -> 둘 중 큰 걸 선택
                    // 담는다 = dp[i - 1][j - (i 무게)] + i의 가치
                    int notSelected = (i == 0) ? 0 : dp[i - 1][j]; // 담지 않는다
                    int selected = (i == 0) ? item[i][1] : dp[i - 1][j - item[i][0]] + item[i][1]; // 담는다

                    dp[i][j] = Math.max(selected, notSelected);
                }
            }
        }

        System.out.print(dp[N-1][K]);
    }
}