[BOJ] 평범한 배낭 (12865)

✍ 백준 알고리즘 문제풀이

Kotlin 문법을 심화하기 위한 알고리즘 풀이입니다.

문제 개요

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

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

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

문제 정리

입력

N = 물품의 개수 (1 ≤ N ≤ 100)
K = 준서가 버틸 수 있는 무게 (1 ≤ K ≤ 100,000)
W = 물건의 무게 (1 ≤ W ≤ 100,000)
V = 물건의 가치 (0 ≤ V ≤ 1,000)

출력

준서가 배낭에 넣을 수 있는 물건들의 가치합의 최댓값

풀이 방법

해당 문제는 배낭 채우기 문제로 Brute-Force, Greedy, DP의 풀이 방법이 존재합니다.
하지만 Brute-Force 는 전체를 검사하기에 $O(n^2)$의 시간복잡도를 갖기에 패스하고
Greedy 는 (가치/무게)의 값이 제일 높은 물건부터 담아 답을 구하면
빠르긴하겠지만 그 답이 최적의 답이라고 보장하지 못합니다.
필자는 여기서 DP의 방법을 사용할 것입니다.

DP!

Devide-and-Conquer 원리로 문제의 점화식을 도출해 이전에 계산해둔
값을 메모리에 저장해서 반복 작업을 줄이는 기법(Memoization)이 핵심입니다.

문제를 해석해보면 우리는 두가지 선택 경우가 존재합니다.

• 1. 넣으려는 물건의 무게가 전체 제한 무게를 초과한다면 물건을 넣지 않는다.
• 2. 제한 무게를 초과하지 않는 한 물건을 넣는다.
  • 2-1. 현재 넣으려는 물건의 무게만큼 배낭에서 뺀다 그리고 현재 물건을 넣는다.
  • 2-2. 현재 물건을 넣지 않고 이전 배낭 그대로 가져간다.

이에 따른 점화식을 도출 시
현재 담을 물건의 인덱스 i, 현재 가방 허용 용량 j
현재 담을 물건의 무게 weight, 물건의 가치 value

1. j < weight 시 knap[i][j] = knap[i-1][j]
2. knap[i][j] = max( knap[i-1][ j-weight ]+value ), knap[i-1][j] )

2차원 배열

말로만 설명하기 어려우니 2차원 배열로 살펴보겠습니다.
먼저 무게와 가치에 대한 값을 받고 배낭의 무게당 최대 가치를 저장할 테이블을 만듭니다.

그 뒤 위 점화식을 따라 값을 채워줍니다.
이 때 물건 knap[i][j] 값이 최대 무게에 초과하면 이전 값인 knap[i][j-1] 값을 따라가고
물건 knap[i][j] 가 최대 무게에 초과하지 않으면 max를 통해 물건을 넣지 않은 이전 값과 물건 i를 넣었을 때 가치를 비교하여 더 큰 쪽을 가져옵니다.

해당 예시는 이전 값이 물건 i의 무게를 초과하지 않아
knap[1][4+1] = max( knap[1][5], knap[2-1][ 5 - 4 ] + 8 ) )
다음 점화식을 수행했으며 그로 인해 8이 나온 과정입니다.

이전까지의 무게에 물건 i를 집어 넣을 수 없는 조건이므로 이전 값을 그대로 복사합니다.

그래서 전체 다 채워지면 knap[n][k] 가 정답이 됩니다.

소스 코드

import java.io.StreamTokenizer
import kotlin.math.max

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())){
    fun nextInt() : Int { nextToken(); return nval.toInt() }

    //n = 물품의 수 k = 버틸 수 있는 무게
    val n = nextInt(); val k = nextInt()
    val knap = Array(n+1) { IntArray(k+1) { 0 } }
    //first = 무게 second = 가치
    val thing = Array(n) { Pair(nextInt(), nextInt()) }

    for (i in 1..n) {
        for (j in 0 until k) {
            val weight = thing[i - 1].first
            val value = thing[i - 1].second
            if (j + 1 >= weight) {
                knap[i][j + 1] = max(knap[i - 1][j + 1], knap[i - 1][j + 1 - weight] + value)
            } else {
                knap[i][j + 1] = knap[i - 1][j + 1]
            }
        }
    }
    
    println(knap[n][k])
}