https://www.acmicpc.net/problem/12865
문제
가방과 물건의 정보가 주어지고 물건을 선택했을 때 가장 가치가 높은 경우의 수를 출력하는 문제이다
아이디어
DP로 풀면 되겠다고 생각했지만 아이디어가 떠오르지 않아 찾아보니 냅색 알고리즘이라는게 있었다.
냅색 알고리즘에 의하면 물건과 가치를 저장하는 2차원 배열을 생성한 뒤 배열을 탐색하며 가치를 저장해 배열의 마지막 인덱스를 출력하면 그것이 가장 큰 가치를 갖는 경우가 된다.
풀이
먼저 가방의 무게와 물건의 개수만큼의 2차원 배열을 생성한다.
dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
예제를 이용하면 다음과 같은 배열이 나온다.
가방의 무게 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
물건의 개수 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1번 물건 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2번 물건 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3번 물건 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4번 물건 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5번 물건 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
이 배열의 각각의 값은 행을 w 열을 i 라고 했을 때
w의 무게를 가진 가방을 i번째 물건까지 넣었을 때 가지는 최대 가치가 된다
가방에 물건을 넣는 경우의수는 다음과 같다.
1. 물건을 넣지않는 경우
2-1. 물건을 넣는경우
2-2. 다른 물건을 빼고 현재 물건을 넣는경우
1번의 경우는 다음과 같은 조건을 건다.
if j < weight:
dp[i][j] = dp[i - 1][j]
이는 현재의 물건의 무게가 배낭의 최대무게를 초과했을 경우이다.
이 경우는 애초에 물건을 넣을 수 없으므로 이전 물건dp[i-1]의 최대가치 dp[i-1][j]를 가져온다.
2-1과 2-2는 두 경우를 비교해서 큰값을 가지는 경우를 선택하면된다.
dp[i][j] = max(value + dp[i - 1][j - weight], dp[i - 1][j])
value + dp[i - 1][j - weight]은 물건을 넣는경우이고
dp[i-1][j]는 물건을 넣지 않았을 경우이다.
이 때 j-weight을 하는 경우는 물건이 들어갈 공간을 확보하기 위해서이다. i-1(이전 물건을 넣는경우)의 j-weight(현재 물건을 넣을 공간을 확보한 경우)의 값에서 value값을 더한것이다.
그렇게 배열을 순회하고 배열의 끝을 출력하면 된다.
해당 배열을 표로 만들면 다음과 같다.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
weight | value | ||||||||
6 | 13 | 0 | 0 | 0 | 0 | 0 | 13 | 13 | |
4 | 8 | 0 | 0 | 0 | 8 | 8 | 13 | 13 | |
3 | 6 | 0 | 0 | 6 | 8 | 8 | 13 | 14 | |
5 | 12 | 0 | 0 | 6 | 8 | 12 | 13 | 14 |
코드
N, K = map(int, input().split())
backpack = [[0,0]]
for _ in range(N):
backpack.append(list(map(int, input().split())))
dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
for j in range(1, K + 1):
weight = backpack[i][0]
value = backpack[i][1]
if j < weight:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(value + dp[i - 1][j - weight], dp[i - 1][j])
print(dp[N][K])
'알고리즘' 카테고리의 다른 글
[백준 파이썬] 1865 웜홀 (2) | 2023.12.08 |
---|---|
[백준 파이썬] 2644 촌수계산 (1) | 2023.12.06 |
[백준 파이썬] 17216 가장 큰 감소 부분 수열 (0) | 2023.12.01 |
[백준 파이썬] 9465 스티커 (1) | 2023.11.29 |
[백준 파이썬] 13549 숨바꼭질 3 (0) | 2023.11.17 |