조연섭의 IT 블로그 :: [알고리즘] algosopt - 여행 짐 싸기 (동적계획법)

728x90

여행 짐 싸기

문제 정보

시간 제한	메모리 제한
2000ms	65536kb

문제

여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 캐리어를 하나만 가지고 갈 수 있는데, 아무래도 가져가고 싶은 물건들이 캐리어 안에 다 들어가지 않을 것 같습니다. 재훈이는 가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를 조사해 다음과 같은 목록을 만들었습니다.

물건	노트북 컴퓨터	카메라	XBOX365	커피그라인더	아령	백과사전
부피	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 이하의 자연수입니다.

출력

각 테스트 케이스별 출력의 첫 줄에는 가져갈 수 있는 물건들의 최대 절박도 합과 가져갈 물건들의 개수를 출력합니다. 이후 한 줄에 하나씩 각 물건들의 이름을 출력합니다. 만약 절박도를 최대화하는 물건들의 조합이 여럿일 경우 아무 것이나 출력해도 좋습니다.

예제 입력

2
6 10
laptop 4 7
camera 2 10
xbox 6 6
grinder 4 7
dumbell 2 5
encyclopedia 10 4
6 17
laptop 4 7
camera 2 10
xbox 6 6
grinder 4 7
dumbell 2 5
encyclopedia 10 4

예제 출력

24 3
laptop
camera
grinder
30 4
laptop
camera
xbox
grinder

문제 풀이

다음 물건을 고를때와 고르지 않을 때를 비교하여 최대 절박도를 리턴해주는 최대 절박도 계산 (pack) 함수를 만든다.
현재 순번 N과 그 다음 순번 N + 1을 pack 함수를 호출하여 비교하여 같지 않은 경우 결과값 (picked)에 담아주는 재귀 함수 (recursive_pack)를 만든다.
재귀 함수 (recursive_pack)를 호출하여 결과 값을 출력하는 solution 함수를 만들어 최초 호출한다.

전체 코드

def pack(total_weight, weights, needs, index):
    if index == len(weights) - 1 or total_weight == 0:
        return 0

    if weights[index + 1] > total_weight:
        return pack(total_weight, weights, needs, index + 1)

    return max(needs[index] + pack(total_weight - weights[index], weights, needs, index + 1), pack(total_weight, weights, needs, index + 1))
               
               
def recursive_pack(total_weight, weights, needs, index, picked = []):
    
    if index == len(weights) - 1 or total_weight == 0:
        return picked
        
    if pack(total_weight, weights, needs, index) == pack(total_weight, weights, needs, index + 1):
        return recursive_pack(total_weight, weights, needs, index + 1, picked)
    else:
        picked.append(index)
        return recursive_pack(total_weight - weights[index], weights, needs, index + 1, picked)
        
def solution(total_weight, names, weights, needs):
    sum_needs = 0
    pack_names = []
    rst = recursive_pack(total_weight, weights, needs, 0, [])
    for index in rst:
        pack_names.append(names[index])
        sum_needs += needs[index]
        
    print(sum_needs, len(pack_names))
    for pack_name in pack_names:
        print(pack_name)
        
        
# 예제 1)
names = ['lasttop', 'camera', 'xbox', 'grinder', 'dumbell', 'encyclopedia']
needs = [7, 10, 6, 7, 5, 4]
weights = [4, 2, 6, 4, 2, 10]
total_weight = 10
solution(total_weight, names, weights, needs)
# lasttop
# camera
# grinder
# 24

# 예제 2)
names = ['lasttop', 'camera', 'xbox', 'grinder', 'dumbell', 'encyclopedia']
needs = [7, 10, 6, 7, 5, 4]
weights = [4, 2, 6, 4, 2, 10]
total_weight = 17
solution(total_weight, names, weights, needs)
# lasttop
# camera
# xbox
# grinder
# 30

참고자료