알고리즘

소개

로봇의 최소이동경로 알고리즘.
0-1 knapsack 문제

알고리즘 소스와 분석 및 time complexity
실행화면 포함

목차

1. 로봇의 최소 이동경로 구하기
2. 0-1 knapsack 문제

본문내용

1. 로봇의 최소 이동경로 구하기
-W[][] : 인접행렬 저장배열
-D[][] : 최단거리 저장배열
-minimum(int a, int b) : 작은 정수 return하는 함수
-void print_array(int a[][N+2])
void print_array2(int a[][N+2]) : 배열출력함수
-void floyd(int n, const int W[][N+2],int D[][N+2]) : floyd알고리즘함수

● 16개의 정점사이의 이음선의 가중치를 인접행렬로 만들어 준 후(W) 정점을 거쳐 가는 것이 좋은지 거쳐 가지 않는 것이 좋은지 비교한 후 계속 업데이트해준다.

● 분석 - floyd알고리즘 : n³
- 배열 출력함수 : n²

● time complexity : O(n³)


2. 0-1 knapsack 문제
-P[n][w] : 처음부터 n개까지의 아이템에 대해서 무게가 w를 넘지 않도록 선택했을 때의 최대의 이익
- P[n-1][w]: n번째 아이템을 넣지 않은 경우의 최대 이익
-: n번째 아이템을 넣은 경우의 최대 이익
-재귀 관계식을 이용하여 knapsack함수를 불러온다.

참고자료

· 없음