[Swift] 백준_평범한 배낭(12856)(knapsack)

문제

 

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

12865번: 평범한 배낭

 

 

풀이

 

knapsack이라는 유명한 문제라고한다. 문제와 똑같이 가방 안에 물건을 넣을 때, 최대 무게를 넘지 않고 최대의 가치를 구하는 문제이다. 

 

풀이를 이해하기가 쉽지 않아서 자료를 많이 찾아봤던 것 같다.(내 머리가 모자라다는걸 다시 한 번 느낄 수 있었음)

 

일단 이 문제는 knapsack 문제 중에서도 0/1 knapsack이라고 불리는 문제이다. knapsack 문제에는 넣을 물건을 나눌 수 있는 경우와 없는 경우가 있는데, 이 문제처럼 물건을 나눌 수 없는 경우를 0/1 knapsack이라고 한다.

 

아무튼 이 문제를 해결하기 위해서는 dp가 쓰인다. 그냥 조합을 찾아도 되지만 시간복잡도가 굉장히 크기 때문에 dp를 이용한다.

 

 

총 n개의 물건이 있고, 최대 무게는 k라고 가정하고 첫 번째 물건부터 확인해보자.

 

첫 번째 물건은 무게가 a이고, 가치가 b이다. 0/1 knapsack문제라는 것을 생각하면 이 물건을 가방에 넣을때와 안넣을 때로 나눌 수 있다. 우선 넣는 경우를 생각해보자.

가방 안에 물건을 넣기 위해서는 일단 가방에 들어갈 수 있는 최대 무게 k보다 첫 번째 물건의 무게가 가벼워야한다. 만약 k보다 첫 번쨰 물건의 무게인 a가 더 크다면 가방 안에 첫 번째 물건을 넣을 수 없게 되어 최대 가치는 0이 되고, 아직 k의 무게를 이용할 수 있다.

하지만 a가 k보다 작다면, 가방안에 물건을 넣냐 안넣냐 이렇게 두 가지 선택지가 존재한다. 만약 물건을 넣지 않는다면 위와 동일하게 최대 가치는 0이고, k의 무게를 이용할 수 있게 된다. 물건을 넣게된다면, 가치는 b가 될 것이고 가방의 여유 무게는 k - a 가 될 것이다.

 

다음으로 무게가 c이고, 가치가 d인 두 번째 물건까지 있는 경우를 생각해보자. 우선, 두 번째 물건부터 넣을지 말지 결정할 것이다. 

현재 가방에는 아무것도 들어있지 않고 두 번째 물건을 안넣는 경우를 생각해보자. 이 경우에는 가방에 들어갈 수 있는 무게가 k인 상태로 첫 번째 물건을 넣을 지 고민할 수 있다. 그리고 두 번째 물건을 안넣는 경우에는 c가 k보다 큰 경우도 포함되어 있다. 

이번에는 두 번째 물건을 넣는 경우를 생각해보자. 두 번째 물건을 넣게 되면 가방에 들어갈 수 있는 무게는 k - c가 될 것이다. 이제 이 k - c의 무게로 첫 번째 물건의 경우를 생각하면 되는 것이다.

 

위의 과정을 보면 왜 dp가 이용되는지 알 수 있다.

 

일단 정의하는데 필요한 변수는 확인하는 물건의 범위와 무게이다. 그래서 2차원 배열을 이용할 것이다.

result[n][k]는 가능한 무게가 k일때, n번째(인덱스의 경우에는 n - 1)까지 물건을 확인해서 구한 최대의 가치라고 생각하면 된다. 위의 경우를 생각해보면 result[0][k]은 최대 무게가 k일때, 0번째 물건(첫 번째 물건이라고 생각하면됨)까지 확인해서 구한 가치이다. 

 

문제에 나온 예시를 이용하면 이해하기 쉽다. 최대 무게는 7이고 물건들은 [[6,13],[4,8],[3,6],[5,12]]와 같이 주어진 상태이다. 

최대 무게가 0일때부터 차례대로 확인해보자. k부터 확인하는게 아니라 아래서부터 확인하는 이유는 그래야 dp를 이용해 값을 구할 수 있기 때문이다.

result[0][0]은 0번째 물건인 [6,13]까지만 확인했을 때 넣을 수 없으므로 0이된다. 마찬가지로 result[0][5]까지는 0이되고,

result[0][6]은 물건을 넣을 수 있으므로 해당 물건의 가치인 13이 된다. result[0][7]까지 올라가도 현재까지 담을 수 있는 물건은 첫 번째 물건밖에 없으므로 result[0][7]도 13이 된다.

 

다음으로, result[1][0]은 최대 무게가 0일때 1번째 물건인 [6,13],[4,8]까지 확인한 경우이다. 1번째 물건을 우선으로 생각하고 진행하면 된다. 당연히 4짜리는 넣을 수 없으므로 result[1][3]까지는 0이된다.

result[1][4]부터는 이제 1번째 물건을 넣을지 말지 선택할 수 있게 된다. 그래서 만약 넣는다고 할 경우엔 result[1][4]의 값은 1번째 물건의 가치인 8에 다가 result[0][0]을 더해주면 된다. 

result[0][0]을 더해주는 이유는, 1번째 물건을 확인했으므로 이전의 물건인 0번째까지의 물건을 확인하면 되기 때문인데 이때 무게는 4에서 1번째 물건의 4를 빼준 0이라서 result[0][0]을 더해주는 것이다.

result[1][5]를 보면 이해가 된다. result[1][5]도 마찬가지로 1번째 물건을 넣을 수 있게 된다. 그래서 만약 넣는 경우엔 result[0][5-4]가 되는 것이다. 하지만 만약 넣지 않는 경우에는 최대 무게 그대로 이전 물건을 확인하면 되므로 result[0][5]의 값이 되는 것이다.

 

 

확실하게 이해하기 위해서 설명하는 것처럼 글을 썼지만 정리안된 글이라 나만 이해할 수 있을 것 같다... 아무튼 위의 내용을 코드로 구현하면 다음과 같다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = input[0]
let k = input[1]
var items: [[Int]] = []
var result = Array(repeating: Array(repeating: 0, count: k + 1), count: n + 1)
for _ in 0..<n {
    items.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
for i in 0..<n {
    for j in 1...k {
        if i == 0 {
            if j >= items[i][0] {
                result[i][j] = items[i][1]
            }
        } else {
            result[i][j] = items[i][0] <= j ? max(items[i][1] + result[i - 1][j - items[i][0]], result[i - 1][j]) : result[i - 1][j]
        }
    }
}
print(result[n - 1][k])

 

 

_____________________________________________________________________________________________________

 

 

머리가 나쁜 것을 다시 한 번 느낄 수 있는 문제였다.