📒 문제 설명
🔖 https://www.algospot.com/judge/problem/read/PACKING
📖 문제
여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 캐리어를 하나만 가지고 갈 수 있는데, 아무래도 가져가고 싶은 물건들이 캐리어 안에 다 들어가지 않을 것 같습니다. 재훈이는 가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를 조사해 다음과 같은 목록을 만들었습니다.
물건 노트북 컴퓨터 카메라 XBOX 커피 그라인더 아령 백과사전 부피 4 2 6 4 2 10 절박도 7 10 6 7 5 4
캐리어의 용량이 정해져 있기 때문에 가져갈 수 있는 물건들의 부피 합은 캐리어의 용량 w 이하여야 합니다. 이때 절박도를 최대화할 수 있는 물건들의 목록을 계산하는 프로그램을 작성하세요.
✍ 입력
입력의 첫 줄에는 테스트 케이스의 수 C (1≤C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 가져가고 싶은 물건의 수 N (1≤N≤100)과 캐리어의 용량 W (1≤W≤1000)가 주어집니다. 그 이후 N줄에 순서대로 각 물건의 정보가 주어집니다. 한 물건에 대한 정보는 물건의 이름, 부피, 절박도 순서대로 주어지며, 이름은 공백 없는 알파벳 대소문자 1글자 이상 20글자 이하의 문자열, 부피와 절박도는 1000 이하의 자연수입니다.
💻 출력
각 테스트 케이스별 출력의 첫 줄에는 가져갈 수 있는 물건들의 최대 절박도 합과 가져갈 물건들의 개수를 출력합니다. 이후 한 줄에 하나씩 각 물건들의 이름을 출력합니다. 만약 절박도를 최대화하는 물건들의 조합이 여럿일 경우 아무 것이나 출력해도 좋습니다.
✏️ 풀이 과정
📝 접근
- 대표적인 배낭 문제(Knapsack Problem)로, 그중에서도 각 물건을 최대 하나만 고를 수 있는 0/1 배낭 문제이다.
- 0/1 배낭 문제의 최적해를 구하기 위해서는 현재
item_index에 해당하는 물건을 담는 경우와 담지 않는 경우를 비교하여, 각 경우에서 최대 절박도가 더 큰 것을 택하면 된다.
cache[capacity][item_index]는item_index번 물건까지 확인했을 때, 남은 부피capacity에서의 최대 절박도를 저장한다.
reconstruct의 구현은 교재를 참고하였다.solve(capacity, item_index + 1)과solve(capacity, item_index)이 같은 지를 비교하여, 두 값이 같지 않다면item_index에 해당하는 아이템을 선택하여야만 최대 절박도를 얻을 수 있다는 뜻이므로picked배열에 추가한다.
✨ 소스 코드
import sys
input = sys.stdin.readline
def solve(capacity, item_index):
if item_index == N:
return 0
ans = cache[capacity][item_index]
if ans != -1:
return ans
# 이 물건을 담지 않는 경우
ans = solve(capacity, item_index + 1)
# 이 물건을 담는 경우
if capacity >= items[item_index][1]:
ans = max(ans, solve(capacity - items[item_index][1], item_index + 1) + items[item_index][2])
cache[capacity][item_index] = ans
return ans
def reconstruct(capacity, item_index, picked):
if item_index == N:
return 0
solved_copy = solve(capacity, item_index)
if solved_copy == solve(capacity, item_index + 1):
reconstruct(capacity, item_index + 1, picked)
else:
picked.append(items[item_index][0])
reconstruct(capacity - items[item_index][1], item_index + 1, picked)
return solved_copy
for _ in range(int(input())):
N, W = map(int, input().split())
items = []
cache = [[-1] * N for _ in range(W + 1)]
for _ in range(N):
item_info = input().split()
# items[i][0]: 물건 이름, items[i][1]: 부피, items[i][2]: 절박도
items.append((item_info[0], int(item_info[1]), int(item_info[2])))
picked = []
print(reconstruct(W, 0, picked), len(picked))
for p in picked:
print(p)
