문제
미리 말하자면, 배낭문제란 알고리즘 유형이 따로 있는데, 나는 그 유형 중에서 해당 문제를 분할 가능한 배낭 문제로 이해하고 접근하였다가, 틀렸다. 이 문제는 0-1 배낭 문제로 접근해야 한다.
나의 코드
def solution():
pass
if __name__ == "__main__":
N, K = map(int, input().split())
backpack = list()
for _ in range(N):
w, v = map(int, input().split())
backpack.append([w,v])
backpack.sort(key=lambda x : (x[0], -x[1]))
# print(backpack)
curr_bpk = 0
value = 0
for item in backpack:
nbp = curr_bpk + item[0]
if nbp <= K:
curr_bpk = nbp
value += item[1]
continue
else:
break
print(value)이렇게 접근한 이유는 이전에 풀었던 배낭 문제가 위와 같은 방법으로 문제를 해결했기 때문이다. 결국 나는 배낭 문제 유형을 제대로 숙지하지 못한 것이 틀린 이유라고 볼 수 있다.
위의 문제는 정렬한 뒤에, 넣을 수 있는 만큼 넣어주면 문제가 풀렸다. 이 문제는 분할 가능한 배낭 문제이다. 이런 유형은 그리디로 풀 수 있다. 그리고 지금 풀었던 배낭 문제는 0-1 배낭 문제이다.
GPT가 풀어준 배낭 문제
def knapsack(N, K, items):
# DP 테이블 초기화 (최대 무게 K+1만큼 생성)
dp = [0] * (K + 1)
for w, v in items:
# 뒤에서부터 탐색 (중복 사용 방지)
for weight in range(K, w - 1, -1):
dp[weight] = max(dp[weight], dp[weight - w] + v)
return dp[K]
# 입력 받기
N, K = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]
# 결과 출력
print(knapsack(N, K, items))점화식+DP로 문제를 풀어주었는데, 정말 천재라는 생각 밖에 안든다..
여기서 느낀 점은 DP와 점화식은 접점이 많다는 것이다. 왜냐하면 DP를 하기 위해선 memorization이 필요하다. 그리고 점화식은 f(n+1) = f(n) + k 처럼 이전 항과 현재 항의 관계를 파악하는 것이기 때문에, f(n)을 어딘가에 저장해둬야 한다. 결론적으로는 이런 유형은 이렇게 풀어야 한다라는 것을 GPT부터 배웠다.
상세히 문제 풀이를 서술하자면, 아래의 코드가 핵심이다.
dp[weight] = max(dp[weight], dp[weight - w] + v)dp에는 무게까지 넣을 수 있는 최대의 값을 저장한다. 그런데, 차근차근 dp를 채울 수 있도록 뒤에서부터 탐색하며 배낭에 물건을 넣어주었고, 그리고 max 함수를 통해 dp가 이전 값(memorization)과 현재 내가 넣어볼려고 하는 값을 서로 비교한 뒤에, 가장 큰 값을 넣을 수 있도록 해주었다. 사실은 이게 전부이고, 핵심 아이디어이다.
고찰
- 배낭 문제는 아래와 같은 세부 유형으로 나눠져 있다.
a. 분할 가능한 배낭 문제- 선형 계획법 문제 유형과 유사하다. 이때 K 무게 만큼 채울 수 있을 때, A 아이템이 총 X kg만큼 있고, 1kg당 Y 만큼의 가치가 있어서, 이를 kg당 배낭에 담을 수 있을 때, 해당되는 문제 유형이다. 이는 맨처음에 내가 푼 대로 가치를 기준으로 정렬한 뒤에, 최대한 배낭에 담아주면 된다.
- 이 문제 유형은 GPT가 풀어준 대로, DP를 사용하면 된다. 이때, 뒤에서부터 탐색해줘야 하며, 내가 넣을려는 물품과 이전 최대값을 비교해봐야 한다.
