[알고스팟/ALGOSPOT] 10. PACKING

알고리즘 알고파! 알고라파덕

안녕하세요~ 알고라파덕입니다!

이번 10번 문제는 PACKING이라는 문제입니다.!!

이 문제는 동적계획법 대표 문제입니다. 가방 문제라고도 불리구요!

입력에서 테스트 케이스가 주어집니다. 테스트 케이스당 물건의 개수 N과 가방의 용량 W가 주어집니다

그리고 N개의 줄에 걸쳐 물건의 이름과 부피, 절박도(가치)가 주어집니다.

N개의 물건을 용량내로 최대한의 가치, 절박도로 채워야 하는 것이 목표입니다.

최대 가치와, 물건 개수, 물건의 이름들을 출력해야 합니다. (경로 추적이 필요합니다~)

최대 가치만 구하라 하면 동적계획법만을 사용하면 되지만, 물건의 개수와 이름을 구해야하기 때문에

추가적으로 재귀함수를 이용하여 경로를 추적합니다.

동적 계획법 부분

점화식 1번 : sum[i-1][data[i].volume]과 data[i].value 비교

sum[i-1][data[i].volume] < data[i].value => sum[i][data[i].volume] = data[i].value

뜻 : i번째 부피와 i번 이전까지의 물품들을 조합해서 만든 부피가 같은 곳에서 이전까지의 물품들의

가중치 합이 i번째 물건 가중치보다 작은 경우에는 i번째 물건을 넣어 가중치를 높인다.

sum[][]배열을 바로 위 칸의 값을 가지고와 정보를 누적한다.

점화식 2번 sum[i-1][j]가 존재하고 sum[i-1][j] + data[i].value > sum[i][j+data[i].volume]이고 j+data[i].volume <= 총용량 일 경우에는

sum[i][j+data[i].volume] = sum[i-1][j] + data[i].value

뜻 : i 이전까지의 물건들을 사용하여 만든 부피에서 i번째 물건을 넣는다고 할 때, i전까지의 물건들을 사용하여 똑같은 부피를 만든 것 보다 가중치가 높으면 가중치를 바꿔준다.

이 2점화식을 반복해주면 마지막 줄에는 부피마다 최대값을 구할 수 있다.

그래서 마지막 줄에서 가장 최대인값을 출력을 하면 최대 절박도가 나온다.

재귀함수 추적부분

추적 방법으로는 점화식 1번이나 2번을 사용하여 물건을 가방에 집어넣을 때, 추적 배열을 하나

생성하여 그 칸에 물건의 부피 값을 넣어둔다.

그렇게 되면 왼쪽과 같은 추적배열이 만들어지는데 여기서 최대값이 나왔던 지점에서

재귀함수로 역추적을 한다. 동그라미친 (6,10) 번째에서 시작을 한다.

0이라는 것은 물건을 사용하지 않은 것이므로 바로 위칸으로 올라가고

0이 아니라는 것은 그 부피의 물건을 사용한것이므로 윗 행의 부피값 만큼 왼쪽인 곳으로 올라간다.

그런방법으로 행번호가 1보다 작게되면 리턴을 하면서 값어치가 있던 부분의 문자열을 출력한다.

동적계획법도 시험이 끝나는대로 설명을 올리도록 하겠습니다~!

알고라파덕의 알고스팟 알고파