1. 개요
이 문제는 0-1 배낭 문제(Knapsack Problem) 로, 대표적인 동적 계획법(Dynamic Programming, DP) 문제이다.
2. 문제 정리
- 물품 수 (N) (1 ≤ (N) ≤ 100): 최대 100개의 물건이 있음.
- 배낭이 버틸 수 있는 무게 (K) (1 ≤ (K) ≤ 100,000): 최대 100,000까지 가능.
- 각 물건의 무게 (W) (1 ≤ (W) ≤ 100,000) 와 가치 (V) (0 ≤ (V) ≤ 1,000) 가 주어짐.
- 목표: 배낭에 넣을 수 있는 물건들의 가치 합의 최댓값 구하기.
3. 해결 방법
이 문제는 동적 계획법(DP, Dynamic Programming) 을 이용해 해결하는 것으로, 앞서 0-1 배낭문제라 함은 각 개체를 넣고 빼고를 계산하여 갱신하는 의미로써의 0 1 이라고 생각하면 된다.
DP를 사용하는 이유:
- 가능한 배낭의 최대 무게가 100,000으로 매우 크기 때문에, 모든 경우의 수를 탐색하는 완전 탐색(Brute Force)은 시간 초과가 발생하기 때문.
- 따라서, 배낭의 최대 무게를 기준으로 최적 부분 문제(optimal substructure)를 이용하는 DP를 사용해야 함.
4. DP 접근법
배낭 문제를 푸는 방법 중 하나는 1차원 DP 배열을 사용하는 방법이다.
DP 배열 정의
dp[j]를 무게 제한이 (j)일 때 얻을 수 있는 최대 가치라고 본 문제에서는 정의하자.
- 예를 들어,
dp[5] = 12라면 배낭의 무게가 5일 때 얻을 수 있는 최대 가치는 12라는 의미이고 - 최종적으로
dp[K]가 우리가 구해야 하는 정답(배낭에 담을 수 있는 최대 가치) 이다. - 우리는 여기서
dp[K]에 대해 각 물건들을 하나씩 넣고 빼며 계속해 갱신해서 나갈 것이다
4.2 점화식
각 물건 를 배낭에 추가할지 말지를 결정할 때, 다음 점화식을 사용할 수 있다.
dp[j] = max(dp[j], dp[j - W] + V)풀이하자면
- dp[j]: 현재까지 구한 무게 (j)일 때 최대 가치.
- dp[j - W] + V: 현재 무게 (j)에서 새로운 아이템을 추가했을 때의 가치.
- 즉, 현재 물건을 배낭에 넣는 경우와 안 넣는 경우 중 더 큰 값을 선택.
를 의미하는데, j j - w 자체가 현재 무게와 넣으려는 무게 만큼을 빼고 + V (그 무게를 지닌 아이템의 가치)를 더하여 계산하는 것이기에 수식 자체는 어렵지 않다.
다만 중요한 것은 dp[j]가 현재까지 구한 무게 j 일때의 최대 가치라는 것을 인지하는 것
4.3 구현 방식
이 문제에서는 배낭의 무게 제한 (K)부터 거꾸로(j를 감소시키면서) DP를 갱신해야 한다.
왜냐하면
- 만약
dp[j]를 증가하는 순서로 갱신하면, 같은 물건이 여러 번 추가되는 문제가 생기기 때문이다. (이전j - 1을 참조하므로) - 내림차순으로 갱신하면, 같은 물건이 한 번만 추가되는 효과가 있습다.
5. Python 코드 설명
import sys
def main():
N, K = map(int, sys.stdin.readline().rstrip().split())
dp = [0] * (K + 1) # 무게 K 까지 저장할 DP 테이블을 초기화하고
for _ in range(N): # N개 의 물건 갯수만큼 루프를 돌리는데 해당 물건을 매번 넣고 빼고를 DP 테이블 통해 정함
w, v = map(int, sys.stdin.readline().rstrip().split()) # 각 물건의 무게와 가치
# DP테이블을 갱신해준다. 무게 K에서부터 w까지 거꾸로 탐색
for j in range(K, w - 1, -1):
# 현재 아이템을 넣은 경우 vs 넣지 않은 경우를 비교
# 수식을 보면 알겠지만 딱 w 만큼 dp 무게 차이가 난다.
# 최종적으로 dp[K]가 갱신 되어야 하는 것인데
# 이중 루프를 돌며 각 아이템을 넣고 안 넣은 상태에 대하여 비교하며
# 갱신 이전 값과 현재 추가되는 물품의 무게치 만큼 뺀 가방 가용량의 dp값을 더해
# max로 비교하여 dp를 갱신하게 됨.
dp[j] = max(dp[j], dp[j - w] + v)
print(dp[K])
if __name__ == "__main__":
main()6. 코드 실행 과정
예제 입력
4 7
6 13
4 8
3 6
5 12- 4개의 아이템, 배낭의 최대 무게 7.
- (무게 6, 가치 13), (무게 4, 가치 8), (무게 3, 가치 6), (무게 5, 가치 12)
DP 배열 갱신 과정
초기 상태:
dp = [0, 0, 0, 0, 0, 0, 0, 0] # 크기 K+1 (0~7)1) 첫 번째 물건 (무게 6, 가치 13)
-
무게 7부터 6까지 갱신
# 무게가 7로 꽉차는 경우, 이전 7(현재 아무것도 안 넣음) # 또는 무게 1 찬거에 무게 6(가치 13)넣은 거랑 비교 dp[7] = max(dp[7], dp[1] + 13) = 13 # 무게가 6으로 찬 경우, 이전 6(현재 아무것도 안 넣음) # 또는 무게가 0 찬거에 무게 6(가치 13)넣은 거랑 비교 dp[6] = max(dp[6], dp[0] + 13) = 13# 갱신 dp = [0, 0, 0, 0, 0, 0, 13, 13]
2) 두 번째 물건 (무게 4, 가치 8)
-
무게 7부터 4까지 갱신
# 무게가 7로 꽉 차는 경우, 이전 7(첫번째 물건 들어감) # 또는 무게 3 찬거에 무게 4(가치 8)넣은 거랑 비교 (이전 7이 가치가 크기에 그대로 13) dp[7] = max(dp[7], dp[3] + 8) = 13 # 무게가 6으로 찬 경우, 이전 6(첫번째 물건 들어감) # 또는 무게 2로 찬거에 무게 4(가치 8)넣은 거랑 비교 (이전 6이 가치가 크기에 그대로 13) dp[6] = max(dp[6], dp[2] + 8) = 13 # 무게가 5로 찬 경우, 이전 5(아무것도 안 들어감) # 또는 무게 1로 찬거에 무게 4(가치 8)넣은 거랑 비교 (하나라도 물건 들어간게 크기에 8) dp[5] = max(dp[5], dp[1] + 8) = 8 # 동일 매커니즘. dp[4] = max(dp[4], dp[0] + 8) = 8dp = [0, 0, 0, 0, 8, 8, 13, 13]
3) 세 번째 물건 (무게 3, 가치 6)
# 무게가 7로 꽉 찬 경우에 이전 무게 7 (첫번쨰 물건들어감)과
# 무게 4에 현재 무게 3(가치 6) 넣은 것과 비교 (후자가 커서 14로 갱신)
# 이렇게 갱신될수 있었던 것은 윗 단계에서 하나씩 넣고 빼며 dp[4]를 갱신해 놨기 때문
# 결국 최종적으로 dp[7]을 갱신하는 것인데 그걸 갱신하기 위해 계속 하나씩 넣고 빼며 dp테이블 최종치를 계산하고 있는 것
dp[7] = max(dp[7], dp[4] + 6) = 14
# 이하 동일 메커니즘...
dp[6] = max(dp[6], dp[3] + 6) = 13
dp[5] = max(dp[5], dp[2] + 6) = 8
dp[4] = max(dp[4], dp[1] + 6) = 8
dp[3] = max(dp[3], dp[0] + 6) = 6dp = [0, 0, 0, 6, 8, 8, 13, 14]4) 네 번째 물건 (무게 5, 가치 12)
dp[7] = max(dp[7], dp[2] + 12) = 14
dp[6] = max(dp[6], dp[1] + 12) = 13
dp[5] = max(dp[5], dp[0] + 12) = 12dp = [0, 0, 0, 6, 8, 12, 13, 14]최종적으로 dp[7] = 14가 출력
7. 시간 복잡도 분석
- DP 테이블 크기: (O(K))
- N개의 물건을 순회: (O(N))
- 각 물건마다 DP 배열을 갱신: (O(K))
- 총 시간 복잡도: () (최대 (), 충분히 해결 가능)
헤매는 만큼 자기 땅이다.