12865번: 평범한 배낭

평범한 배낭

 

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제 입력 1 복사

4 7
6 13
4 8
3 6
5 12

예제 출력 1 복사

14

---

풀이

문제를 잘 확인해야 한다. 

 

1. N개의 물품 수가 주어지고 K는 준서가 버틸 수 있는 무게이다.
2. N개의 물품 중 준서가 버틸 수 있는 무게에서 가치합의 최댓값을 구해라.

처음 이 문제를 읽고 1부터 N까지 연속된 무게의 가치합만 가능한 줄 알고 코드를 구현했다.....ㅎ

다시 마음잡고 풀어보다가 계속 답이 안나와 결국 검색을 해봤다.

검색을 통해 확인해보니 Knapsack 알고리즘을 사용한다고 한다.

 

이 문제는 "연속된"이라는 말이 없으니 준서가 버틸 수 있는 무게에서 가치합의 최댓값을 구하면 된다. 

 

---

설계

 

이제 문제를 이해했으니 어떻게 구현할지 생각해보자.

문제의 핵심은 준서가 버틸 수 있는 무게에서 물품 가치를 더한 가치합의 최댓값이다.

 

• 무게가 1, 2, .. K일 때까지
• 1번 물품만 넣은 경우, 2번 물품까지 넣은 경우 ... N번 물품까지 넣은 경우

와 같이 dp 테이블을 작성할 수 있다.

dp 테이블 작성하는 과정은 아래의 블로그를 참고하였다.

 

[백준,BOJ 12865] 평범한 배낭(JAVA 구현, 추가풀이)

 

🔎 예제에 따라 dp 테이블을 작성하는 과정을 알아보자.

4 7
6 13
4 8
3 6
5 12

 

1️⃣

1번 item인 경우 무게, 가치 순으로 (6, 13)을 의미한다. 무게 6부터 N인 7까지 가치 13을 다 채운다.

 

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item	0	0	0	0	0	13	13
2번 item
3번 item
4번 item

 

2️⃣

 2번 item인 경우(4, 8)을 의미한다. 무게 1부터 무게 3까지는 이전 dp값을 가져온다. 무게 4부터 N까지 8로 다 채우는 데 이전 dp에 저장된 무게 6과 무게 7의 가치가 8보다 더 크므로, 이전 값을 가져온다. 

 

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item	0	0	0	0	0	13	13
2번 item	0	0	0	8	8	13	13
3번 item
4번 item

 

3️⃣

3번 item인 경우 (3, 6)을 의미한다. 무게 1과 2는 이전 dp값을 가져오고, 무게 3부터 N까지 6으로 다 채우는 데 무게 7은 무게 3과 무게 4의가치를 더한 값이 이전 dp 값보다 더 크므로 14를 저장한다.

 

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item	0	0	0	0	0	13	13
2번 item	0	0	0	8	8	13	13
3번 item	0	0	6	8	8	13	14
4번 item

 

4️⃣ 

4번 item인 경우 (5, 12)을 의미하고, 위와 같은 방식으로 채워 넣어보면 최종적으로 아래와 같은 dp 테이블이 나온다. 

 

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item	0	0	0	0	0	13	13
2번 item	0	0	0	8	8	13	13
3번 item	0	0	6	8	8	13	14
4번 item	0	0	6	8	12	13	14

 

 

---

구현

 

위의 설계 단계에서 알아본 dp 테이블을 코드로 구현해보자.

동적계획법의 bottom-up 방식을 이용하여 풀었다.

 

✏️ 점화식

: 이전에 dp에 저장된 무게의 가치 값과 현재 자신의 가치와 비교하여 큰 값을 dp에 저장한다.

dp[i][j] = max(dp[i-1][j], arr[i][1] + dp[i-1][j-arr[i][0]])

 

 

---

전체코드

 

var Input = readLine()!.split(separator: " ").map{Int(String($0))!}

var (N, K) = (Input[0], Input[1])

var arr : [[Int]] = Array(repeating: Array(repeating: 0, count: 2 ), count: N+1)
var dp : [[Int]] = Array(repeating: Array(repeating: 0, count: K+1 ), count: N+1)

for i in 1..<N + 1{
    let nInput = readLine()!.split(separator: " ").map{Int(String($0))!}
    arr[i][0] = nInput[0]
    arr[i][1] = nInput[1]
}

for i in 1..<N + 1{
    for j in 1..<K + 1{
        if j-arr[i][0] >= 0 {
            dp[i][j] = max(dp[i-1][j], arr[i][1] + dp[i-1][j-arr[i][0]])
        }else{
            dp[i][j] = dp[i-1][j]
        }
    }
}

print(dp[N][K])