[2023-05-01] 12865 평범한 배낭 (Kotlin) + 1문제

 

문제 링크: https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

 

첫 번째 시도입니다.

 

문제 유형을 보지 않고 풀었고, dfs를 이용하였습니다.

 

package thirtyFirst
import java.io.*
fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n,k) = br.readLine().split(' ').map{it.toInt()}
    val bag = arrayListOf<Pair<Int,Int>>()
    repeat(n){
        val (w,v) = br.readLine().split(' ').map{it.toInt()}
        bag.add(Pair(w,v))
    }
    // (0,0)으로 초기화, first는 무게, second는 가치
    val arr = Array(n){Pair(0,0)}
    val visit = Array(n){false}
    var max = 0
    
    fun dfs(num: Int, prevSize: Int){
        if (num == n){
            var sum = 0
            
            // 실험상 출력해보기
            arr.forEach{print("$it ")}
            println()
            
            //가치의 최대값을 max에 저장
            arr.forEach{sum += it.second}
            max = Math.max(sum,max)
            return
        }
        
        for (index in bag.indices){
            if (!visit[index]){
            	// 다음 물건의 무게를 수용할 수 없을 때
                // 배열에 (0,0)을 넣기
                if ((prevSize + bag[index].first) > k){
                    arr[num] = Pair(0,0)
                    visit[index] = true
                    dfs(num + 1, prevSize)
                    visit[index] = false
                }
                else{
                    visit[index] = true
                    arr[num] = bag[index]
                    dfs(num + 1, prevSize + bag[index].first)
                    visit[index] = false
                }
            }
        }
    }
    dfs(0,0)
    println(max)
}

 

 

다음은 입력에 대한 출력값입니다.

 

// 입력
// 4 7
// 6 13
// 4 8
// 3 6
// 5 12

// 출력
(6, 13) (0, 0) (0, 0) (0, 0) 
(6, 13) (0, 0) (0, 0) (0, 0) 
(6, 13) (0, 0) (0, 0) (0, 0) 
(6, 13) (0, 0) (0, 0) (0, 0) 
(6, 13) (0, 0) (0, 0) (0, 0) 
(6, 13) (0, 0) (0, 0) (0, 0) 
(4, 8) (0, 0) (3, 6) (0, 0) 
(4, 8) (0, 0) (0, 0) (3, 6) 
(4, 8) (3, 6) (0, 0) (0, 0) 
(4, 8) (3, 6) (0, 0) (0, 0) 
(4, 8) (0, 0) (0, 0) (3, 6) 
(4, 8) (0, 0) (3, 6) (0, 0) 
(3, 6) (0, 0) (4, 8) (0, 0) 
(3, 6) (0, 0) (0, 0) (4, 8) 
(3, 6) (4, 8) (0, 0) (0, 0) 
(3, 6) (4, 8) (0, 0) (0, 0) 
(3, 6) (0, 0) (0, 0) (4, 8) 
(3, 6) (0, 0) (4, 8) (0, 0) 
(5, 12) (0, 0) (0, 0) (0, 0) 
(5, 12) (0, 0) (0, 0) (0, 0) 
(5, 12) (0, 0) (0, 0) (0, 0) 
(5, 12) (0, 0) (0, 0) (0, 0) 
(5, 12) (0, 0) (0, 0) (0, 0) 
(5, 12) (0, 0) (0, 0) (0, 0) 
14

 

무게가 초과되지 않는 선에서 최대값을 구할 수 있었습니다.

 

하지만 시간초과가 떴습니다.

 

 

 

두 번째 시도입니다. dp로 풀어보려고 시도했습니다.

 

package thirtyFirst
import java.io.*
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n, k) = br.readLine().split(' ').map { it.toInt() }
    val bag = arrayListOf<Pair<Int, Int>>()
    repeat(n) {
        val (w, v) = br.readLine().split(' ').map { it.toInt() }
        bag.add(Pair(w, v))
    }
    bag.sortWith(compareBy<Pair<Int,Int>>{it.first}.thenBy{it.second})
    val dp = Array(n){Pair(0,0)}
    
    if (bag.first().first <= k)
        dp[0] = bag.first()
        
    for (index in 1 until bag.size){
        if (dp[index-1].first + bag[index].first > k){
            var max = 0
            for (index1 in index-1 downTo 0){
                val second = dp[index-1].second - bag[index1].second + bag[index].second
                val first = dp[index-1].first - bag[index1].first+bag[index].first
                if (first <= k){
                    if (max <= second){
                        max = second
                        dp[index] = Pair(first,second)
                    }
                }
                else
                    dp[index] = dp[index-1]
            }
        }
        else{
            dp[index] = Pair(bag[index].first+dp[index-1].first, bag[index].second+dp[index-1].second)
        }
    }
    println(dp.maxBy{it.second}.second)
    //77
}

 

논리가 틀렸기 때문에 굳이 적지는 않겠습니다. 

 

한참 생각하다 포기를 했습니다.

 

다른 분의 코드입니다.

 

코드 출처

[boj 12865 / kotlin] 평범한 배낭

 

package thirtyFirst

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.max

var n = 0
var k = 0
lateinit var products: Array<Pair<Int, Int>>

fun main() {
    init()
    solve()
}

fun init() = with(BufferedReader(InputStreamReader(System.`in`))) {
    with(StringTokenizer(readLine())) {
        n = nextToken().toInt()
        k = nextToken().toInt()
    }
    products = Array(n) {
        with(StringTokenizer(readLine())) {
            Pair(nextToken().toInt(), nextToken().toInt())
        }
    }
    close()
}

fun solve() {
    val cache = IntArray(k + 1)

    for (p in products) {
        for (i in k downTo p.first) {
            cache[i] = max(cache[i], cache[i - p.first] + p.second)
        }
    }

    println(cache[k])
}

 

 

아직까지도 완벽하게 이해가 된 것 같지 않습니다.

 

계속 고민해봐야 할 것 같아요.