gold5-12865.md

Baekjoon

평범한 배낭

• 분류: 다이나믹 프로그래밍, 배낭 문제
• 풀이 언어: Swift
• 문제 요약: K만큼의 무게만 들어가는 배낭에 넣을 수 있는 물건들의 최대 가치합 구하기

코드

2차원 배열

let nk = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, k) = (nk.first!, nk.last!)
var w = [Int](repeating: 0, count: n + 1)
var v = [Int](repeating: 0, count: n + 1)
var dp = [[Int]](repeating: [Int](repeating: 0, count: k + 1), count: n + 1)

for i in 1...n {
    let wv = readLine()!.split(separator: " ").map { Int(String($0))! }
    w[i] = wv.first!
    v[i] = wv.last!
}

for i in 0..<n + 1 {
    for j in 0..<k + 1 {
        if i == 0 || j == 0 {
            dp[i][j] = 0
            continue
        }
        if w[i] <= j {
            dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]])
        } else {
            dp[i][j] = dp[i - 1][j]
        }
    }
}

print(dp[n][k])

• 메모리: 141416 KB
• 시간: 284 ms

1차원 배열

let nk = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, k) = (nk.first!, nk.last!)

var items = [(Int, Int)]()
for _ in 0..<n {
    let wv = readLine()!.split(separator: " ").map { Int(String($0))! }
    if wv.first! <= k {
        items.append((wv.first!, wv.last!))
    }
}

var dp = [Int](repeating: 0, count: k + 1)
for (w, v) in items {
    var tmp = dp
    for i in w...k {
        if dp[i] < dp[i - w] + v {
            tmp[i] = dp[i - w] + v
        }
    }
    dp = tmp
}

print(dp[k])

• 메모리: 63808 KB
• 시간: 36 ms

회고

• 처음으로 도전해본 배낭 문제(knapsack problem), 더 정확히 말하면 0-1 배낭문제이다. 처음엔 정답 풀이를 봐도 어떻게 푸는건지 영 감이 잡히질 않았지만 직접 2차원 배열을 그려 값을 하나씩 채워나가다 보니 얼핏 감이 잡히기 시작했다.
• 다만 이 문제는 2차원 배열을 이용해 정석적으로 풀면 메모리와 시간 모두에서 효율이 매우 안 좋다.
  • 일단 dp 배열의 차수를 2차원에서 1차원으로 낮춘다. 2차원 배열의 dp[i][w]가 i번째 물건까지 넣을 수 있고 최대 무게가 w일 때의 최대 가치합을 뜻한다면, 1차원 배열의 dp[w]는 최대 무게가 w일 때의 최대 가치합만을 고려한다.
• 튜플 보다는 두개의 배열을 사용해 푸는 것이 항상 효율이 좋다고 생각했었는데 이 문제에선 그렇지 않았다🤔 (약 8 ms 정도로 차이가 크진 않았지만) 어떤 상황에서 튜플이 효율을 낮추는지 잘 관찰해보아야겠다.