백준 12865번 - 평범한 배낭 (kotlin)

문제

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

유형

다이나믹 프로그래밍 (처음에 Top-Down 방식으로 해결함)

풀이

문제에서 요구하는 것은 배낭의 한도 무게 내에서 물건을 선택해서 가치의 최대값을 만드는 것이다.

가장 간단하고 확실한 방법은 완전 탐색(Brute Force) 즉, 모든 경우의 수를 확인하는 것이다.

문제의 요구 사항을 이렇게 해석할 수도 있다. '한도 내에서 가치의 합이 최대가 되도록 물건의 조합을 만들어라.' 그러면 완전탐색을 수행하는 방법은 각 물건마다 배낭에 [넣는 경우/넣지 않는 경우] 2가지를 모두 선택해보며 조합을 만드는 것이 된다.

시간 복잡도는 어떻게 될까? n개의 물건 모두 2가지를 케이스를 확인하므로 O(2^n)이 된다. n<=100이므로, 최악의 경우 시간 안에 정답을 확인할 수 없다.

어떻게 시간을 줄일 수 있을까? 완전 탐색의 시간 복잡도를 줄이는 대표적인 방법은 다이나믹 프로그래밍이다.

다이나믹 프로그래밍은 부분 계산 결과를 저장해놓고 같은 계산이 필요할 때 중복 계산을 진행하지 않고 저장된 값을 활용한다. 그럼 먼저 부분 결과를 저장할 배열을 정의해야 하는데, 아래와 같이 할 수 있다.

maxValueSum[k][i]: 배낭의 무게 한도가 k일 때, [i, n-1] 범위의 물건으로 만들 수 있는 가치의 최대값

참고로 Top-Down 방식을 기준으로 정의한 것이다.

배열의 변수는 배낭의 한도 무게와 물건의 인덱스이다. 물건을 배낭에 넣으면 남은 한도 무게가 변하고, 선택 가능한 물건의 범위가 변하므로 합당한 듯 하다.

이렇게 배열을 정의하면 어떤 식으로 중복되는 부분 문제가 발생할까?

위와 같이 입력이 주어졌다고 가정하자. n=10, k=30, 물건[0]의 무게=3, 물건[1]의 무게=7이다.

[0,3]범위의 물건 중 물건[1]만 선택한 경우에 대한 가치의 최대 값은? 물건[1]의 가치 + 배낭 한도 23과 물건[4,9]로 만들 수 있는 가치의 최대값(maxValueSum[23][4])과 같다.

그리고 여기서 maxValueSum[23][4]을 계산해 놓으면, 다음에 물건[0]과 물건[2]를 선택한 경우에도 배낭 무게가 7이 되므로 maxValueSum[30-7][4]를 곧장 사용할 수 있다.

그럼 이제 배열에 대한 점화식을 정의해보자.

maxValueSume[k][i] =
if (k >= weight[i]): max(maxValueSum[k][i+1], maxValueSum[k - weight[i]][i+1] + value[i]),
else: maxValueSum[k][i+1]

i번째 물건을 배낭에 넣는 것과 넣지 않는 케이스 중 최대 값을 의미하며, else문은 배낭 한도가 물건의 무게보다 작아서 넣을 수 없는 케이스이다.

시간 복잡도는 얼마나 단축 됐을까?
Top-Down: 배열의 크기 x 함수 내의 연산 횟수
Bottom-Up: 배열의 크기 x 반복문 내의 연산 횟수
==> 100,000 x 100 x 2 = O(K x N x 2) = O(KN)이다.
시간 안에 답을 구할 수 있다.

위 알고리즘을 구현한것을 아래의 kotlinfun calculateMaxValueSum(weightLimit: Int, stuffIndex: Int): Int 에서 확인할 수 있다.

코드 (Kotlin)

(1) Top-Down

data class Stuff(val weight: Int, val value: Int)

lateinit var stuffArray: Array<Stuff>
lateinit var maxValueSumCache: Array<IntArray>

fun main() {
    val (stuffCount, weightLimit) = readln().split(" ").map(String::toInt)
    stuffArray = Array(stuffCount) {
        readln().split(" ").run {
            Stuff(weight = this[0].toInt(), value = this[1].toInt())
        }
    }
    maxValueSumCache = Array(weightLimit + 1) {
        IntArray(stuffCount) { -1 }
    }

    calculateMaxValueSum(weightLimit, 0).let {
        println(it)
    }
}

fun calculateMaxValueSum(weightLimit: Int, stuffIndex: Int): Int {
    if (weightLimit <= 0 || stuffIndex >= stuffArray.size) {
        return 0
    }
    if (maxValueSumCache[weightLimit][stuffIndex] != -1) {
        return maxValueSumCache[weightLimit][stuffIndex]
    }

    val stuff = stuffArray[stuffIndex]

    maxValueSumCache[weightLimit][stuffIndex] = calculateMaxValueSum(weightLimit, stuffIndex + 1)
    if (weightLimit >= stuff.weight) {
        maxValueSumCache[weightLimit][stuffIndex] = maxOf(
            maxValueSumCache[weightLimit][stuffIndex],
            stuff.value + calculateMaxValueSum(weightLimit - stuff.weight, stuffIndex + 1)
        )
    }

    return maxValueSumCache[weightLimit][stuffIndex]
}

(2) Bottom-Up

data class Stuff(val weight: Int, val value: Int)

fun main() {
    val (stuffCount, weightLimit) = readln().split(" ").map(String::toInt)
    val stuffArray: Array<Stuff> = Array(stuffCount) {
        readln().split(" ").run {
            Stuff(weight = this[0].toInt(), value = this[1].toInt())
        }
    }
    val maxValueSum: Array<IntArray> = Array(weightLimit + 1) {
        IntArray(stuffCount)
    }
    
    for (w in stuffArray[0].weight..weightLimit) {
        maxValueSum[w][0] = stuffArray[0].value
    }
    
    for (tempWeightLimit in 1..weightLimit) {
        for (i in 1 until stuffCount) {
            maxValueSum[tempWeightLimit][i] = maxValueSum[tempWeightLimit][i - 1]
            if (tempWeightLimit >= stuffArray[i].weight) {
                maxValueSum[tempWeightLimit][i] = maxOf(
                    maxValueSum[tempWeightLimit][i], 
                    stuffArray[i].value + maxValueSum[tempWeightLimit - stuffArray[i].weight][i - 1]
                )
            }
        }
    }

    print(maxValueSum[weightLimit][stuffCount - 1])
}