문제
최대의 가치를 구하라
입력
첫 번째 줄은 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다.
두 번째 줄부터 각 보석의 무게와 가치가 주어진다.
가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다.
출력
첫 번째 줄에 가방에 담을 수 있는 보석의 최대가치를 출력한다.
정답 풀이
- 냅색 알고리즘을 이용한다.
- 첫번째 보석만을 이용했을 때 최댓값 각 배열에 초기화
- 두번째 보석도 이용했을 때 최댓값 각 배열에 초기화
...- 모든 보석을 이용했을 때 최댓값 각 배열에 초기화 가능
정답 코드
import sys
sys.stdin = open("input.txt", "rt")
def input():
return sys.stdin.readline().rstrip()
if __name__ == "__main__":
n, m = map(int,input().split())
dy = [0] * (m+1);
for i in range(n):
w,v=map(int,input().split())
for j in range(w,m+1):
dy[j] = max(dy[j], dy[j-w]+v) # 현재 값 VS 빈공간 무게 + 현재 값 중에 큰 값으로 최대값 초기화
print(dy[m])코멘트
냅색 알고리즘 설명
냅색 알고리즘은 담을 수 있는 물건이 나눌 수 있냐 없냐에 따라 나눈다.
담을 수 있는 물건이 나누어 질 때(설탕 몇 g 등): 분할가능 배낭문제(Fractional Knapsack Problem)
담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 0-1 배낭문제(0-1Knapsack Problem)
해당 문제는 0-1 배낭문제의 경우다.
이 문제는 다음과 같은 알고리즘으로 풀 수 있다. 풀어서 한 번, 식으로 한 번 설명하겠다.
알고리즘
1) x축엔 가방 1~K 까지의 무게, y축은 물건 N개 개수 만큼의 배열을 만들어준다.
2) 행을 차례대로 돌며 다음과 같은 알고리즘을 수행해준다.
3-0) 현재 물건이 현재 돌고있는 무게보다 작다면 바로 [이전 물건][같은 무게] (knapsack[i-1][j]를 입력해준다.
3-1) 현재 물건을 넣어준다. 물건을 넣은 뒤의 남은 무게를 채울 수 있는 최댓값(knapsack[i-1][j-weight]을 위의 행에서 가져와 더해준다.
3-2) 현재 물건을 넣어주는 것보다. 다른 물건들로 채우는 값(knapsack[i-1][j])을 가져온다.
4) 3-1과 3-2 중 더 큰 값을 knapsack[i][j]에 저장해준다. 이 값은 현재까지의 물건들로 구성할 수 있는 가장 가치 높은 구성이다.
5) knapsack[N][K]는 곧, K무게일 때의 최댓값을 가리킨다.
수식
결국 수식으로 표현하면 다음과 같다.
knapsack[i][j] = max(현재 물건 가치 + knapsack[이전 물건][현재 가방 무게 - 현재 물건 무게], knapsack[이전 물건][현재 가방 무게])
knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])
결국 아래와 같은 엑셀이 만들어진다.
