[백준] 12865 - 평범한 배낭
1. 문제
2. 개요
냅색 알고리즘을 활용하는 dp문제.
가방의 최대무게와 물건을 각각 행,열로 하는 표를 만들어보자.
| 6 / 13 | 4 / 8 | 3 / 6 | 5 / 12 | |
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| 5 | ||||
| 6 | ||||
| 7 |
각 물건은 가방의 최대무게가 물건의 무게 이상인 경우에만 들어갈 수 있다.
첫 물건부터 넣어보자.
| 6 / 13 | 4 / 8 | 3 / 6 | 5 / 12 | |
|---|---|---|---|---|
| 1 | 0 | |||
| 2 | 0 | |||
| 3 | 0 | |||
| 4 | 0 | |||
| 5 | 0 | |||
| 6 | 13 | |||
| 7 | 13 |
이어서 두 번째 물건을 넣어보자.
| 6 / 13 | 4 / 8 | 3 / 6 | 5 / 12 | |
|---|---|---|---|---|
| 1 | 0 | 0 | ||
| 2 | 0 | 0 | ||
| 3 | 0 | 0 | ||
| 4 | 0 | 8 | ||
| 5 | 0 | 8 | ||
| 6 | 13 | 13 | ||
| 7 | 13 | 13 |
최대 무게가 6, 7 인 경우, 두번째 물건을 그냥 넣게 되면 최대 무게를 초과하게 된다.
따라서 이런 경우, 이미 들어있는 물건을 빼고 현재 물건을 넣거나, 넣지 않거나 선택을 해야 한다.
전 물건을 넣던 상황에서 현재 물건의 무게를 뺀 최대무게의 가치 + 현 물건의 가치와 전 물건의 지금 고려하는 최대무게의 상황을 비교해야 한다.
최대 무게 6의 경우
→ 첫 물건 최대무게 2의 상황 (0) + 현 물건의 가치 (8)와 최대 무게 6인 경우 첫 물건의 상황(13)
최대 무게 7의 경우
→ 첫 물건 최대무게 3의 상황 (0) + 현 물건의 가치 (8)와 최대 무게 7인 경우 첫 물건의 상황(13)
둘 다 후자가 더 가치가 크므로 칸에는 13이 들어간다.
| 6 / 13 | 4 / 8 | 3 / 6 | 5 / 12 | |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | |
| 2 | 0 | 0 | 0 | |
| 3 | 0 | 0 | 6 | |
| 4 | 0 | 8 | 8 | |
| 5 | 0 | 8 | 8 | |
| 6 | 13 | 13 | 13 | |
| 7 | 13 | 13 | 14 |
세 번째 물건의 최대 무게 7의 경우도 위와 같이 해결한다.
첫 물건 최대무게 4의 상황 (8) + 현 물건의 가치 (6)와 최대 무게 7인 경우 두번째 물건의 상황(13)
14 > 13 이므로 칸에는 14가 들어가게 된다.
같은 방식으로 마지막까지 완성하면
| 6 / 13 | 4 / 8 | 3 / 6 | 5 / 12 | ||
|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | |
| 2 | 0 | 0 | 0 | 0 | |
| 3 | 0 | 0 | 6 | 6 | |
| 4 | 0 | 8 | 8 | 8 | |
| 5 | 0 | 8 | 8 | 12 | |
| 6 | 13 | 13 | 13 | 13 | |
| 7 | 13 | 13 | 14 | 14 |
3. 코드 및 추가내용
3-1. 시도 1
import sys
N, K = map(int,sys.stdin.readline().split())
items = []
for i in range(N):
W, V = map(int,sys.stdin.readline().split())
items.append([W, V])
dp = [[0 for i in range(K+1)] for i in range(N+1)]
for i in range(1, N+1):
for j in range(items[i-1][0], K+1):
dp[i][j] = max(dp[i-1][j], items[i-1][1] + dp[i-1][j - items[i-1][0]])
print(max(dp[-1]))
첫 시도 실패.
문제가 뭔지 찾아보려고 만들어진 dp테이블을 살펴본 결과
j의 범위를 지정할 때 시작위치를 현재 물건의 무게부터 시작했더니, 현재 물건보다 가벼운 무게의 물건으로 만든 경우를 가져오지 못하는 상황이 발생하여 실패.
3-2. 시도 2
import sys
N, K = map(int,sys.stdin.readline().split())
items = []
for i in range(N):
W, V = map(int,sys.stdin.readline().split())
items.append([W, V])
dp = [[0 for i in range(K+1)] for i in range(N+1)]
for i in range(1, N+1):
for j in range(1, K+1):
if j >= items[i-1][0]:
dp[i][j] = max(dp[i-1][j], items[i-1][1] + dp[i-1][j - items[i-1][0]])
else:
dp[i][j] = dp[i-1][j]
print(max(dp[-1]))
그래서 j를 전체범위(0은 안넣는 경우이기 때문에 제외) 로 설정하고 현재 물건의 무게보다 가벼운 경우라면 dp테이블의 전 행의 같은 열의 결과를 그대로 가져오는 방법으로 통과했다.
Comments