동적 알고리즘, 되추적 알고리즘 사용

소개글

●기름 값 문제 해결에서 이용되는 알고리즘 비교 고찰

●문제
제주도에 휴가를 간 뒤 자동차를 렌트하여 제주도를 돌아다니려고 한다. 최소비용의 기름 값을 구하기 위하여 어느 곳에서 얼 만큼의 기름을 넣어야 되는지 알아보자.
자동차의 기름통은 200L이고 처음 자동차를 빌렸을 때 100L의 기름이 있었다. 그러므로 반납 할 때에도 100L의 기름이 있어야 하며 제주도에서의 자동차로 돌아다닐 코스는 아래 그림과 같다.(총 거리 500Km)

시 작

7번주유소
1L = 1400

6번주유소
1L = 1020

5번주유소
1L = 1010

4번주유소
1L = 1000

3번주유소
1L = 777

2번주유소
1L = 888

1번주유소
1L = 999




위의 문제에 대하여 두 가지 알고리즘(동적계획법, 되추적)을 이용하여 설계 전략을 세우고, 알고리즘을 바탕으로 현재의 프로젝트를 완성한다. 그리하여 두 가지 알고리즘에 대하여 효율성을 알 수 있고, 스스로의 실력향상을 이룰 수 있다.

컴파일 실행환경

Visual 6.0

압축파일 내 파일목록

동적 알고리즘, 되추적 알고리즘 사용.hwp
backtracking.c
dynamic.cpp

참고 자료

없음