14. 동적 계획법 1
CLASS 4 ESSENTIAL
그 유명한 배낭 문제입니다. 우선 정석은 가로가 K+1, 세로가 N+1인 DP 배열을 사용합니다. 각 원소 a[i][j]의 의미는 i번째 물품까지 탐색했을 때 j 이하의 무게로 만들 수 있는 최대 가치입니다. 먼저 a[0]은 모두 0으로 채웁니다(탐색한 물건이 없습니다). 그리고 a[i][j]는 j가 i번째 물건의 무게보다 작다면 a[i-1][j], 크다면 a[i-1][j]과 a[i-1][j-w]+v 중 큰 값을 저장합니다. 이 규칙으로 DP 배열을 꽉 채운 후 a[N][K]값을 출력합니다.
하지만 문제의 조건을 보면 메모리 제한이 512MB로, int를 1억 3천만개 정도 저장할 수 있습니다. 문제의 조건을 최대로 맞추면 int를 1억개 저장하게 되는데, 약간 애매할 수가 있습니다. 혹시 몰라서 저는 (K+1)×(N+1) DP 배열 대신 길이 N+1 배열 하나로 처리했습니다. 위의 규칙에서 a[i][j]는 바로 이전 줄의 무게가 j 이하인 부분인 a[i-1][0..j]의 범위의 변수로만 정의가 되기 때문에, j를 역방향으로 순회하면서 값을 업데이트하면 순서 꼬임없이 처리가 가능합니다. 이 방법을 사용하여 메모리를 2MB 이내로 사용할 수 있었습니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| C++ | 코드(Github) / 코드(백준) | 2020-04-01 12:50:12 |