[C언어, 알고리즘] knapsack algorithm

목차

<Traveling Salesperson>
1) 프로그램 개요
「문제 풀이」
2) 함수설명
3) 소스 코드
4) 출력화면
5) 고찰

본문내용

1) 프로그램 개요
W의 행렬에서 각 행과 열을 vertex라고 보고 0이면 자기 자신 weight가 있으면 그 weight로 연결되어 있다고 생각하자. 이 연결된 vertex에서 한 지점을 선택해 다른 vertex들을 거쳐 다시 돌아오는 프로그램이다. (단, 각 vertex는 한번만 거친다.) 그때 거친 vertex들의 weight을 합친 값이 최소가 되는 것이 프로그램의 결과값이다.
간단히 예를 보이겠다. 출발점을 v1이라고 하고 v2~v5개의 vertex가 있다. v1 -> {v2, v3, v4, v5} ->v1으로 되는 형태이다. 이제 중간에 들어가는 {v2, v3, v4, v5}에서 무엇이 먼저 오느냐에 따라 최종 결과값이 달라진다. 즉, {v2, v3, v4, v5}에서 하나씩 순서를 나열하는 것이다. 문제는 이것을 하나씩 나열하는 경우 모두를 생각했을땐 어마어마하게 많은 계산 과정을 거쳐야 한다는것이다. 그것을 줄이기 위해 Dynamic programming을 사용한다. 즉, 처음부터 {v2, v3, v4, v5} 의 원소들이 다 있다고 생각하는것이 아니라. {v2}만 있다고 생각하고 v1->v2->v1을 계산해보고 {v3]을 넣어보고, 이번엔 {v2,v3} 두 개의 경우를 생각해 보는 식으로 하나씩 늘려가서 이전 결과값들을 사용해 최종 결과값을 도출해 내는 것이다.

키워드

knapsack,   knapsack Algorithm,   algorithm,   알고리즘,   C언어,   프로그램