백준 12865 평범한 배낭
23 Jun 2021https://www.acmicpc.net/problem/12865
이 문제 역시 DP Algorithm에서 설명한 내용이다. 입출력 부분이 추가된 전체 코드만 올리겠으니 자세한 풀이는 DP Algorithm을 참조하길 바란다.
- 전체 코드
let nk = readLine()!.split(separator: " ").map{Int($0)!}
let n = nk[0]
let k = nk[1]
var arr = Array(repeating: 0, count: k+1)
var WV:[(w:Int, v:Int)] = []
for _ in 1...n {
let line = readLine()!.split(separator: " ").map{Int($0)!}
WV.append((w:line[0], v:line[1]))
}
for wv in WV {
let w = wv.w, v = wv.v
if w > k {continue}
var tmp = arr
for i in w...k {
if arr[i] < arr[i-w] + v {
tmp[i] = arr[i-w] + v
}
}
arr = tmp
}
print(arr[k])