Home 백준 - 12865 평범한 배낭 풀이
Post
Cancel

백준 - 12865 평범한 배낭 풀이

문제

12865 평범한 배낭

screencapture

풀이

1. 알고 있어야 할 점

  • 다이나믹 프로그래밍을 이용한다.
    • 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.[동적 계획법]
    • 수식 식 $\newline n:\;담을\,수\,있는\,물건의\,수(담을\,수\,있는\,물건의\,번호:\,0 \leq i \leq n-1)$
      $w:\;버틸\,수\,있는\,무게$
      $i:\;물건의\,번호$
      $max(i): 담을\,수\,있는\,물건의\,번호\,중\,최댓값(max(i) = n-1)$
      $P_{n,\;w}:\;n개의\,물건을\,담을\,수\,있고,\,버틸\,수\,있는\,무게가\,w인\,배낭에\,넣을\,수\,있는\,물건들의\,가치합의\,최댓값$
      $V_i:\;i\,물건이\,가치$
      $W_i:\;i\,물건의\,무게$
  • 문제의 예제 1의 연산 과정
  • Dynamic Programming

2. Step by Step

재귀를 사용하는 방법(timeout 발생)

1. 입력을 받는다.

  • code ```kotlin val (numOfItems, maxWeight) = readln().split(“ “).map { it.toInt() } val items = Array(numOfItems) { readln().split(“ “).let { Item(it.first().toInt(), it.last().toInt()) } }

data class Item(val w: Int, val v: Int)

1
2
3
4
5
6
7
8
9
#### 2. 수식을 재귀 함수로 작성한다.
- code
```kotlin
fun p(n: Int, w: Int, items: Array<Item>): Int = when {
    n == 0 || w == 0 -> 0
    items[n-1].w <= w -> kotlin.math.max(p(n-1, w-items[n-1].w, items) + items[n-1].v, p(n-1, w, items))
    else -> p(n-1, w, items)
}

3. 결과 값을 출력한다.

  • code
    1
    
    println(p(numOfItems, maxWeight, items))
    

반복문을 사용하는 방법

1. 입력을 받는다.

  • code ```kotlin val (numOfItems, maxWeight) = readln().split(“ “).map { it.toInt() } val items = Array(numOfItems) { readln().split(“ “).let { Item(it.first().toInt(), it.last().toInt()) } }

data class Item(val w: Int, val v: Int)

1
2
3
4
5
6
7
### 2. 가치합의 최댓값 저장할 변수를 선언한다.
- 정수형 2차원 배열을 이용한다.
- 배열의 각 값은 0으로 초기화 한다.
- code
```kotlin
val p = Array(numOfItems + 1) { IntArray(maxWeight + 1) { 0 } }

2. 수식을 반복문으로 작성한다.

  • 배열을 0으로 초기화 하였기 때문에 n=0, w=0인 경우에 대해서는 이미 0이 입력되어 있다.
  • 그러므로, 1부터 반복문을 시작한다.
  • code
    1
    2
    3
    4
    5
    6
    
    for(n in (1..numOfItems)) {
      for(w in (1..maxWeight)) {
          val item = items[n-1]
          p[n][w] = if(w >= item.w) kotlin.math.max(p[n-1][w-item.w] + item.v, p[n-1][w]) else p[n-1][w]
      }
    }
    

3. 결과 값을 출력한다.

  • code
    1
    
    println(p(numOfItems, maxWeight, items))
    

kotlin code: 재귀를 사용하는 방법(timeout 발생)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fun main() {
    val (numOfItems, maxWeight) = readln().split(" ").map { it.toInt() }
    val items = Array(numOfItems) { readln().split(" ").let { Item(it.first().toInt(), it.last().toInt()) } }

    println(p(numOfItems, maxWeight, items))
}

data class Item(val w: Int, val v: Int)

private fun p(n: Int, w: Int, items: Array<Item>): Int = when {
    n == 0 || w == 0 -> 0
    items[n-1].w <= w -> kotlin.math.max(p(n-1, w-items[n-1].w, items) + items[n-1].v, p(n-1, w, items))
    else -> p(n-1, w, items)
}

kotlin code: 반복문을 사용하는 방법

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
fun main() {
    val (numOfItems, maxWeight) = readln().split(" ").map { it.toInt() }
    val items = Array(numOfItems) { readln().split(" ").let { Item(it.first().toInt(), it.last().toInt()) } }

    println(p(numOfItems, maxWeight, items))
}

data class Item(val w: Int, val v: Int)

private fun p(numOfItems: Int, maxWeight: Int, items: Array<Item>): Int {
    val p = Array(numOfItems + 1) { IntArray(maxWeight + 1) { 0 } }

    for (n in (1..numOfItems)) {
        for (w in (1..maxWeight)) {
            val item = items[n - 1]
            p[n][w] = if (w >= item.w) max(p[n - 1][w - item.w] + item.v, p[n - 1][w]) else p[n - 1][w]
        }
    }
    
    return p.last().last()
}

Reference

Attachments

This post is licensed under CC BY 4.0 by the author.

백준 - 7576 토마토 풀이

kotlin 제곱 사용법