[백준] 12865 평범한 배낭 python 풀이

문제

• 난이도: 골드5
• 알고리즘 분류: 다이나믹 프로그래밍, 배낭 문제
• 요약: 배낭에 넣을 수 있는 무게의 최댓값이 주어지고 일정 무게와 가치가 있는 짐이 있을 때, 가치의 합이 최대가 되도록 하는 값을 출력하기

 

풀이

Knapsack 문제

배낭에 넣을 수 있는 무게의 최댓값이 주어지고 일정 무게와 가치가 있는 짐이 있다. 이때, 최대 용량을 초과하지 않으면서 배낭에 넣을 수 있는 최대 가치의 합을 찾는 문제이다.

배낭에 짐을 넣을 때, 짐을 쪼갤 수 있는 경우와 쪼갤 수 없는 경우가 존재한다.

• 쪼갤 수 있는 경우 -> 분할가능 배낭문제 (Franction Knapsack Problem)
• 쪼갤 수 없는 경우 -> 0-1 배낭문제 (0-1 Knapsack Problem)

이 문제는 0-1 배낭문제로, 각 물건에 대해 넣기/안넣기 두가지 선택지만 존재한다. 0-1 배낭 문제는 동적계획법(dp)로 해결할 수 있다.

 

최대 7kg를 넣을 수 있는 배낭의 최대 가치를 구하는 거를 예시로 들어보자.
-> 3kg(value:4) + 최대 4kg를 넣을 수 있는 배낭의 최대 가치
-> 3kg(value:4) + 2kg(value:3) + 최대 2kg을 넣을 수 있는 배낭의 최대가치
이처럼 큰 문제를 작은 문제로 나누어 해결가능한 dp의 특징을 볼 수 있다.

 

 

dp 풀이

knapsack (n*k)의 2차원 배열을 생성한다.
knapsack[i][k] = 최대 무게가 k인 배낭에서 i번째 물건까지 판단했을 때의 최대 가치

 

배낭에 물건을 넣을 때,
1) 탐색하는 물건의 무게가 최대 배낭 무게를 초과할 경우, 넣지 않는다.
2) 탐색하는 물건의 무게가 최대 배낭 무게를 초과하지 않을 경우,
    a. 현재 탐색하는 물건을 넣지 않는다.
    b. 현재 넣을 물건의 무게만큼 배낭에서 빼고, 현재 탐색하는 물건을 넣는다.

 

4 7
6 13
4 8
3 6
5 12
위의 예제 입력값에 대한 knapsack 값을 표로 정리했다.

 

코드1

# n: 물품의 수
# k: 최대 넣을 수 있는 무게
n, k = map(int, input().split())

stuff = [[0, 0]]
for _ in range(n):
    stuff.append(list(map(int, input().split()))) # [weight, value]

knapsack = [[0] * (k+1) for _ in range(n+1)]

for i in range(1, n+1): # 탐색할 물건의 인덱스
    for j in range(1, k+1): # 현재 넣을 수 있는 최대 무게
        weight = stuff[i][0]
        value = stuff[i][1]

        if weight > j: # 탐색하는 물건의 무게가 최대 배낭 무게를 초과할 경우
            knapsack[i][j] = knapsack[i-1][j] # 이전 가치 유지
        else: # 탐색하는 물건의 무게가 최대 배낭 무게를 초과하지 않을 경우
        	# 1) 넣지 않기 -> 이전 가치 유지
            # 2) 넣기 -> 탐색하는 물건의 가치 + 현재 넣을 물건을 제외하고 탐색하는 물건의 무게를 뺀 무게를 최대 무게로 설정했을 때의 최대 가치
            knapsack[i][j] = max(knapsack[i-1][j], value + knapsack[i-1][j-weight])

print(knapsack[n][k])

메모리와 처리 시간을 줄이기 위해 dict를 활용하여 효율을 개선했다.

 

코드2

n, k = map(int, input().split())

stuff = []
for _ in range(n):
    stuff.append(list(map(int, input().split())))

stuff.sort(reverse=True)

bag = {0: 0} # {value: weight}

for weight, value in stuff:
    temp = {}
    for bag_value, bag_weight in bag.items():
    	next_bag_value = bag_value + value
        next_bag_weight = bag_weight + weight

        # dict.get 메소드
        # 1) 키(next_bag_value)에 해당하는 값 반환
        # 2) 키가 존재하지 않을 경우, k+1 반환
        if bag.get(next_bag_value, k+1) > next_bag_weight:
            temp[next_bag_value] = next_bag_weight
    # dict.update 메소드
    # 1) 키-값 쌍을 추가
    # 2) 이미 존재하는 키일 경우, 새로운 값으로 업데이트
    bag.update(temp)
print(max(bag.keys()))