[BOJ, Python, Swift] 12865 - 평범한 배낭 ( with DP, Knapsack )

12865번: 평범한 배낭

동적 계획법으로 구현할 수 있는 대표적인 문제인 냅색 문제이다. 각 물건을 분할하여 담을 수 있는 배낭 문제는 단순히 가치의 비율을 계산하여 최대부터 넣는 그리디 알고리즘으로 구현할 수 있지만, 분할할 수 없다면 이와 같이 동적 계획법, 혹은 백트래킹으로 구현해야 한다. 해당 포스팅은 동적 계획법으로 구현했으며, 기회가 된다면 백트래킹 방식도 작성해보려 한다.

 

1. 2차원 배열, Bottom Up

2차원 dp배열과, 배낭이 수용할 수 있는 최대 무게를 1부터 해당 무게까지 늘려가며 채워 넣는 방식이다.

import sys
input = sys.stdin.readline

# 물건의 무게, 배낭의 최대 수용 가능 무게
N, K = map(int, input().split())

# idx는 1부터 시작
w = [0 for _ in range(N + 1)]
v = [0 for _ in range(N + 1)]
dp = [[0] * (K + 1) for _ in range(N + 1)]

# 예제) 무게: [0, 6, 4, 3, 5], 가치: [0, 13, 8, 6, 12]
for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())

for i in range(1, N + 1):
    for j in range(1, K + 1):
        if w[i] <= j:
            # i번째 물건이 가방에 들어갈 수 있는 무게면
            # 넣기 전 가방에 넣을 무게를 확보한 배열 dp[i - 1][j - w[i]]
            # 에 새롭게 넣는 놈의 가치를 더한 값과
            # 넣기 전의 가치 합을 비교
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
        else:
            # 안들어가면 이전의 값을 할당
            dp[i][j] = dp[i - 1][j]
print(dp[N][K])

2. 1차원 배열, Top Down

1차원 dp배열과, 배낭이 수용할 수 있는 최대 무게부터 시작하여 계속 값을 경신하는 방식이다. 2차원 배열보다 더 빠르고, 메모리를 덜 잡아먹는다.

import sys
input = sys.stdin.readline

# 물건의 개수와 배낭의 수용 가능 최대 무게
N, K = map(int, input().split())

# idx는 1부터 시작
w = [0 for _ in range(N + 1)]
v = [0 for _ in range(N + 1)]
dp = [0 for _ in range(K + 1)]

# 예제) 무게: [0, 6, 4, 3, 5], 가치: [0, 13, 8, 6, 12]
for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())

# 각 물건의 무게와 가치를 모두 탐색 (w[i], v[i])
for i in range(1, N + 1):
	# Top Down
    for j in range(K, 0, -1):
        if w[i] <= j:
        	# 가방에 들어갈 수 있는 무게면
            # 이 무게를 뺀 가방에 새롭게 넣는 놈의 가치를 더한 값과 현재 값을 비교
            # 경신
            dp[j] = max(dp[j], dp[j - w[i]] + v[i])
print(dp[K])

약 2배 가량의 메모리와 시간 차이가 발생

+ Swift 코드 추가

let input = readLine()!.split { $0 == " " }.map { Int(String($0))! }
let (N, K) = (input[0], input[1])

var W = Array(repeating: 0, count: N + 1)
var V = Array(repeating: 0, count: N + 1)

for i in 1 ... N {
    let T = readLine()!.split { $0 == " " }.map { Int(String($0))! }
    (W[i], V[i]) = (T[0], T[1])
}

var dp = Array(repeating: 0, count: K + 1)

for i in 1 ... N {
    for j in stride(from: K, through: 1, by: -1) {
        if W[i] <= j {
            dp[j] = max(dp[j], dp[j - W[i]] + V[i])
        }
    }
}

print(dp[K])​