(간단 문제) 도둑이 가져갈 수 있는 보석이 루비,다이아몬드,사파이어가 있다고 하고, 가져갈 수 있는 가방의 크기가 8 이라고 하자.
보석 종류 크기 가치 루비 3 6 다이아몬드 4 3 사파이어 5 5 확장 방법:
(해 설)
- 보석이 루비만 있는 경우 가방 크기별 이윤을 구한후
- 보석이 루비,다이아몬드가 있는 경우 가방 크기별 이윤을 구한후
- 마지막으로 보석이 루비,다이아몬드,사파이어인 경우 가방 크기별 이윤을 구한다.
- 보석이 루비(크기 3, 가격 6)하나만 있는 경우 가방 크기별 이윤은 쉽게 구할 수 있다.
가방의 크기 0 1 2 3 4 5 6 7 8
루비 0 0 0 6 6 6 6 6 6
- 보석이 루비,다이아몬드(크기 4 , 가격 3)가 있는 경우 가방 크기별 최대 이윤을 구하면 (다이아몬드 확장)
- 가방의 크기가 6 일 때 보석이 루비 , 다이아몬드가 있는 경우 크기별 최대 이윤을 구하면
가방의 크기 0 1 2 3 4 5 6 7 8
루비 0 0 0 6 6 6 6 6 6 다이아몬드
- 다이아몬드를 가져가는 경우
가방의 크기가 6 이고 , 다이아몬드의 크기가 4 이므로 다이아몬드를 가져가고 남는 가방의크기는 2 이다.
∴ 이윤 = 다이아몬드의 가격 3 + 가방의 크기 2 로 루비는 가져갈수 없으므로 가격은 0 = 총 이윤은 3- 다이아몬드를 가져가지 않는 경우
가방의 크기 6 으로 루비를 가져갈 때의 이윤 6두가지 경우 중 최대 6 이 루비,다이아몬드가 있는 경우 에서 가방의 크기 6 으로 가져갈수 있는 최대 이윤이다.
- 가방의 크기가 7 일 때 보석이 루비 , 다이아몬드가 있는 경우 크기별 최대 이윤을 구하면
- 다이아몬드를 가져가는 경우
가방의 크기가 7 이고 , 다이아몬드의 크기가 4 이므로 다이아몬드를 가져가고 남는 가방의크기는 3 이다.
∴ 이윤 = 다이아몬드의 가격 3 + 남는 가방의 크기 3 으로 이윤 6 = 총 이윤은 9- 다이아몬드를 가져가지 않는 경우
가방의 크기 7 로 루비를 가져갈 때의 이윤 6두가지 경우 중 최대 9 가 루비,다이아몬드가 있는 경우 에서 가방의 크기 7 로서 가져갈수 있는 최대 이윤이다.
- 가방의 크기가 8 일 때 보석이 루비 , 다이아몬드가 있는 경우 크기별 최대 이윤을 구하면
- 다이아몬드를 가져가는 경우
가방의 크기가 8 이고 , 다이아몬드의 크기가 4 이므로 다이아몬드를 가져가고 남는 가방의크기는 4 이다.
∴ 이윤 = 다이아몬드의 가격 3 + 남는 가방의 크기 4 으로 이윤 6 = 총 이윤은 9- 다이아몬드를 가져가지 않는 경우
가방의 크기 8 으로 루비를 가져갈 때의 이윤 6두가지 경우 중 최대 9 가 루비,다이아몬드가 있는 경우 에서 가방의 크기 8 로서 가져갈수 있는 최대 이윤이다.
가방의 크기 0 1 2 3 4 5 6 7 8
이윤 0 0 0 6 6 6 6 6 6 이윤 0 0 0 6 6 6 6 9 9
- 마지막으로 보석이 루비,다이아몬드,사파이어(크기 5 , 가격 5)가 있는 경우 가방 크기별 최대 이윤을 구하면 (사파이어 확장 )
- ...
- 가방의 크기가 6 일 때 보석이 루비 , 다이아몬드,사파이어가 있는 경우 크기별 최대 이윤을 구하면
- 사파이어를 가져가는 경우
가방의 크기가 6 이고 , 사파이어의 크기가 5 이므로 사파이어를 가져가고 남는 가방의크기는 1 이다.
∴ 이윤 = 사파이어 가격 5 + 가방의 크기 1 로 루비,다이아몬드에서의 이윤은 0 = 총 이윤은 5- 사파이어를 가져가지 않는 경우
가방의 크기 6 으로 루비,다이아몬드에서의 이윤 6두가지 경우 중 최대 6 이 루비,다이아몬드,사파이어가 있는 경우 에서 가방의 크기 6 으로 가져갈수 있는 최대 이윤이다.
- 가방의 크기가 7 일 때 보석이 루비 , 다이아몬드,사파이어가 있는 경우 크기별 최대 이윤을 구하면
- 사파이어를 가져가는 경우
가방의 크기가 7 이고 , 사파이어의 크기가 5 이므로 사파이어를 가져가고 남는 가방의크기는 2 이다.
∴ 이윤 = 사파이어의 가격 5 + 남는 가방의 크기 2 으로 이윤 0 = 총 이윤은 5- 사파이어를 가져가지 않는 경우
가방의 크기 7 로 루비.다이아몬드에서의 이윤 9두가지 경우 중 최대 9 가 루비,다이아몬드,사파이어가 있는 경우 에서 가방의 크기 7 로서 가져갈수 있는 최대 이윤이다.
- 가방의 크기가 8 일 때 보석이 루비 , 다이아몬드,사파이어가 있는 경우 크기별 최대 이윤을 구하면
- 사파이어를 가져가는 경우
가방의 크기가 8 이고 , 사파이어의 크기가 5 이므로 사파이어를 가져가고 남는 가방의크기는 3 이다.
∴ 이윤 = 사파이어의 가격 5 + 남는 가방의 크기 3 으로 이윤 6 = 총 이윤은 11- 사파이어를 가져가지 않는 경우
가방의 크기 8 으로 루비,다이아몬드에서의 이윤 9두가지 경우 중 최대 11 이 루비,다이아몬드,사파이어가 있는 경우 에서 가방의 크기 8 로서 가져갈수 있는 최대 이윤이다. 이것이 답이다.
문제의 핵심은 새로 추가한 보석을 가져가는 경우 혹은 아닌 경우 중 최대 값을 구하면서 보석을 하나씩 추가하면서 확장한다.
정리하면 ,
- 점화식 ans[i][j]: 1 ~ i 번째 보석으로 , 가방의 크기 j 로 얻을 수 있는 최대 이윤
ans[i][j] = max(ans[i-1][j] , profit[i] + ans[i-1][j-weight[i]] )
- i 번째 보석을 포함하지 않는 경우 : ans[i-1][j]
- i 번째 보석을 포함하는 경우 : profit[i] + ans[i-1][j-weight[i]] 단, j-weight[i] >= 0
- 답 : 보석의 개수가 m 개이고, 가방의 크기가 n 이라면 ans[m][n]