백준 12865 평범한 배낭

출처: www.acmicpc.net/problem/12865

분류: DP

---

접근방식

디피로 해결할 수 있는 문제였습니다.

디피는 상황에 따른 최대 값을 기록해놓고 더 최적인 경우를 비교하면서 업데이트 해나가는 메모제이션 방식입니다.

이 문제에서는 특정 무게에 최대 가치가 얼마인지 기록해놓으면 되겠네요.

 

테이블에는 현재까지 찾은 최적의 가치가 들어있다고 할 때,

현재 무게 4짜리의 물품으로 테이블의 무게 7 칸을 채우려고 한다면

최적은 테이블의 무게 3짜리 칸 가치 + 현재 물품의 가치 (무게 4)  vs  테이블의 무게 7짜리 칸의 가치

로 생각해볼 수 있습니다.

이런식으로 물품들을 입력받을 때마다 테이블을 업데이트 해나가면됩니다.

물품마다 현재 무게부터 테이블의 끝까지를 업데이트를 해나가야 하는데 테이블을 그대로 하면 중간에 덮어씌워져 버리기 때문에 제대로된 결과를 계산할 수가 없게됩니다.

 

이를 해결하기 위해서 2차원 배열을 만들어서 2차원 배열을 업데이트 해나가는 방식으로 풀 수 있습니다.

var knapDP = [[Int]](repeating: [Int](repeating: 0, count: nk[1]+1), count: nk[0]+1)

for (i, (weight, value)) in products.enumerated() {
    let item = i+1
    
    for k in 1..<nk[1]+1 {
        guard k >= weight else { knapDP[item][k] = knapDP[item-1][k]; continue }
        knapDP[item][k] = max(knapDP[item-1][k], knapDP[item-1][k - weight] + value)
    }
}

 

2차원 배열 대신 원본 배열을 temp에 복사하고 원본과 비교해서 temp를 업데이트 시킨 뒤 끝나고 원본을 업데이트 시켜주는 방식으로 해결하면 1차원 배열로도 풀 수가 있습니다.

var temp = knapDP

for k in weight..<knapDP.count {
    let newWeight = k-weight > 0 ? knapDP[k-weight] + value : value
    if knapDP[k] < newWeight {
        temp[k] = newWeight
    }
}

knapDP = temp

 

해결방법

 

let nk = readLine()!.split(separator: " ").map { Int(String($0))! }

typealias Product = (w: Int, v: Int)
var products = [Product]()

for _ in 0..<nk[0] {
    let d = readLine()!.split(separator: " ").map { Int(String($0))! }
    products.append((d[0], d[1]))
}

var knapDP = [Int](repeating: 0, count: nk[1]+1)

for (weight, value) in products {
    guard weight < knapDP.count else { continue }
    
    var temp = knapDP
    for k in weight..<knapDP.count {
        let newWeight = k-weight > 0 ? knapDP[k-weight] + value : value
        if knapDP[k] < newWeight {
            temp[k] = newWeight
        }
    }
    knapDP = temp
}

print(knapDP.last!)

 

 

배운점

DP는 테이블을 다 채워야 한다... 이상한 짓 하지말자.. 🤦🏻‍♂️