[알고리즘][알고리즘] 동적프로그래밍 PPT파일

소개글

동적프로그래밍 PPT파일

목차

5.1 동적 프로그래밍의 개념
5.2 이항계수
5.3 행렬의 연속적인 곰셈
5.4 최적의 이진 탐색트리
5.5 외판원 문제
5.6 0-1 배낭문제
5.7 최단경로 문제 : Floyd 알고리즘

본문내용

5.6 0-1 배낭문제
0-1 배낭문제는 탐욕적 알고리즘에서
보았듯이 물건의 부분을 조각내서 배낭에
넣는 것을 허용하지 않으며 하나의 물건을
넣을지 넣지 않을지를 결정하여 최적의 원리를
적용함으로써 최적해를 구한다.

결정을 xn, xn-1,.., x1의 순서로 한다고 하며 결정 xn에
대해 살펴보면
xn=0이면 물건n을 배낭에 넣지 않으므로 이익이 전혀 붙지
붙지 않았으며 배낭의 크기는 여전히 M이다.

xn=1이면 물건n을 배낭에 넣으므로 이익은 pn이 되고 배낭의
크기는 M-wn이 된다.

xn에 대한 결정이 이루어진 다음 우리가 해야될 남아있는 결정들
xn-1, xn-2, …, x1은 결정 xn을 한 다음의 배낭문제에 대해서도
최적이 되어야 한다.
그러므로 최적의 원리가 적용된다.

참고 자료

없음