다이나믹 프로그래밍 복습 노트
배낭 문제와 동적 계획법
대부분의 배낭 문제들은 01 배낭으로 변환한 후 복잡도를 최적화하는 방식으로 접근한다.
01 배낭 문제
각 물건은 선택하거나 선택하지 않는 두 가지 경우만 존재한다. 0과 1의 관계에 해당하기 때문에 01 배낭이라고 명칭한다.
dp[i][j]를 앞에서부터 i개의 물건 중容量 j의 배낭이 담을 수 있는 최대 가치라고 정의하자.
i번째 선택지는 i- ...
7월 24일 23:22에 게시됨