백준 12865번 평범한 배낭 Kotlin 구현해 보기

---

```

백준 12865번 평범한 배낭 Kotlin 구현해 보기

```

Kimc Kotlin Study

배워갈 내용

1. 백준 12865번 풀이

---

문제 링크

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

12865번: 평범한 배낭

문제 설명

백준 12865번 평범한 배낭은

난이도 골드 등급의 문제로서

주어진 배낭 무게 한도 내에서 

여러 물건 중 선택하여 최대 가치를 얻는 문제

물건의 수, 무게, 가치, 배낭 무게 한도가 주어짐

입력:
물건 수 N과

배낭 무게 한도 K
N개의 줄에 물건의 

무게 W와 가치 V

 

출력:
배낭에 넣을 수 있는 물건들의 최대 가치 합 출력

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

코드 설명

 

입력을 받고
정해진 조건에 맞춰서 계산을 해서 출력해 주면 되는
문제입니다.

 

---

dp 배열은 물건을 선택하거나 선택하지 않았을 때의 최대 가치를 저장합니다

dp[i][j]는 i번째 물건과 배낭 무게 j일 때의 최대 가치를 나타냅니다.

 

만약 현재 물건을 배낭에 넣을 수 있는 경우(j - items[i - 1].weight >= 0), 두 가지 선택이 있습니다

현재 물건을 배낭에 넣지 않고, dp[i - 1][j]의 최대 가치를 그대로 가져올 수 있습니다
현재 물건을 배낭에 넣고, dp[i - 1][j - items[i - 1].weight] + items[i - 1].value의 가치를 얻을 수 있습니다
두 경우 중에서 더 큰 가치를 dp[i][j]에 저장합니다

모든 물건과 배낭 무게에 대해 계산을 마치면, 

dp[numItems][maxWeight]에 최대 가치가 저장되어 있으며, 

이 값을 반환합니다

한줄요약

가능한 모든 물건 조합을 고려하여 배낭에 넣을 때 얻을 수 있는 최대 가치를 계산합니다.

 

---

 

요즘에는 주석이나 설명 없이 코드로 설명하고자 노력 중입니다
만약 코드가 이해가 안 가시면 댓글 부탁드립니다

코드

import kotlin.math.max

fun main() {
    val inputDto = readInput()
    print(solution(inputDto))
}

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

data class InputDto(
    val numItems: Int,
    val maxWeight: Int,
    val items: List<Item>
) {
    fun findMaxVal(): Int {
        val dp = Array(numItems + 1) { IntArray(maxWeight + 1) }
        for (i in 1..numItems) {
            for (j in 1..maxWeight) {
                dp[i][j] = if (j - items[i - 1].weight >= 0) {
                    max(dp[i - 1][j], dp[i - 1][j - items[i - 1].weight] + items[i - 1].value)
                } else {
                    dp[i - 1][j]
                }
            }
        }
        return dp[numItems][maxWeight]
    }
}

fun readInput(): InputDto {
    val (numItems, maxWeight) = readLine()!!.split(" ").map { it.toInt() }
    val items = List(numItems) {
        val (weight, value) = readLine()!!.split(" ").map { it.toInt() }
        Item(weight, value)
    }
    return InputDto(numItems, maxWeight, items.toList())
}

fun solution(dto: InputDto): Int {
    return dto.findMaxVal()
}

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---