[백준/코틀린] 12865번: 평범한 배낭

링크

12865번: 평범한 배낭

풀이

dp[i][j]: i번째 물건까지 고려했을 때, 배낭 용량이 j일 때의 최대 가치

일명 0-1 배낭(Knapsack) 문제로,
각 물건을 넣지 않거나(0) 넣거나(1) 둘 중 하나를 선택합니다.

출처: Wikipedia: 0-1 Knapsack Problem

모든 물건(i)과 가능한 무게(j)에 대하여 얻을 수 있는 가치의 최댓값을 계산합니다.

물건을 넣지 않는 경우에는 이전 물건(i - 1)까지만 고려한 값이 유지됩니다.
dp[i][j] = dp[i - 1][j]

물건을 넣는 경우에는 해당 물건의 가치(v)에
이전 물건까지의 결과 중 남은 무게(j - w)에 해당하는 최대 가치를 더하게 됩니다.
dp[i][j] = dp[i - 1][j - w] + v

2차원 테이블을 통해 이전 상태를 모두 저장하며 계산할 수도 있지만,
계산에는 직전 상태만 필요하므로 1차원 배열을 사용해 공간 최적화를 할 수 있습니다.

1차원 DP는 반드시 뒤에서부터 갱신해야 합니다.
앞에서부터 갱신하면 같은 물건을 여러 번 선택한 값이 섞일 수 있습니다.

• 코드 1: 2차원 DP
• 코드 2: 1차원 DP

코드 1: 2차원 DP

fun main() {
    val (n, k) = readln().split(" ").map { it.toInt() }
    val dp = Array(n + 1) { IntArray(k + 1) }

    for (i in 1..n) {
        val (w, v) = readln().split(" ").map { it.toInt() }

        for (j in 1..k) {
            dp[i][j] = if (j < w) dp[i - 1][j]
            else maxOf(dp[i - 1][j], dp[i - 1][j - w] + v)
        }
    }

    println(dp[n][k])
}

코드 2: 1차원 DP

fun main() {
    val (n, k) = readln().split(" ").map { it.toInt() }
    val dp = IntArray(k + 1)

    repeat(n) {
        val (w, v) = readln().split(" ").map { it.toInt() }

        for (j in k downTo w) {
            dp[j] = maxOf(dp[j], dp[j - w] + v)
        }
    }

    println(dp[k])
}