0-1 knapsack 문제에 대한 Dynamic Programming과 Backtracking과 Branch-and-Bound 알고리즘의 실행시간 비교(소스와 결과캡쳐 포함)

소개

정보통신공학(혹은 컴퓨터공학)의 알고리즘 과제로 나온

0-1 knapsack 문제에 대한 Dynamic Programming과 Backtracking과 Branch-and-Bound 알고리즘의 실행시간 비교(소스와 결과캡쳐 포함)

의 과제에 대한 레포트 입니다. 실행시간을 정확하게 측정 및 그래프화 하였고, 소스와 결과캡쳐도 되어있습니다.
만점 받은 과제물입니다.

목차

0-1 배낭채우기에 대한 설명

Dynamic Programming을 통한 알고리즘

Backtracking(되추적)을 통한 알고리즘

Branch-and-Bound를 통한 알고리즘

각 알고리즘의 실행시간 측정 및 그래프화

각 실행시간 비교 및 결과고찰

본문내용

● 0-1 배낭채우기(0-1 Knapsack Problem)
0-1 배낭채우기란 다름과 같다. 어떤 도둑이 한 보석상에 배낭을 메고 침입했다고 하자. 훔친 아이템의 총 무게가 배낭의 용량 W를 초과하면 배낭이 망가진다. 각 아이템의 값어치와 무게는 알고 있다고 한다. 이 밤손님의 딜레마는 총 무게가 W를 초과하지 않으면서 아이템의 총 값어치가 최대가 되도록 아이템을 배낭에 담는 것이다. 이 문제를 0-1배낭채우기 문제라고 한다.
본 과제는 앞에서 설명한 두가지 알고리즘(되추적, 분기한정법)을 0-1 배낭채우기 문제를 통하여 특성과 실행시간을 비교한다. 즉, 각 알고리즘의 아이템 개수가 늘어나는 데 따른 실행시간의 증가 추세와 두 알고리즘간의 우열을 비교할 것이다.

Dynamic Programming 알고리즘을 적용한 0-1 Knapsack
● Program 1 :
- : 처음부터 n개까지의 아이템에 대해서 무게가 w를 넘지 않도록 선택했을 때의 최대의 이익
- : n번째 아이템을 넣지 않은 경우의 최대 이익
- : n번째 아이템을 넣은 경우의 최대 이익
- 위의 Recursive Property를 이용하여, 0부터 n까지의 해당 값을 채워 나간다.
- 어떤 P[n][w]를 요구할 경우, 위의 식에서 계산된 값을 제공한다.
★source code ; 입력1

중략

Backtracking 알고리즘을 적용한 0-1 Knapsack
● Program 1 : Algorithm 5.7을 이용하여 0-1 Knapsack Problem을 위한 프로그램 작성
- state space tree에서 검사되는 node들을 차례대로 (i , j) 형태로 출력
- soulution은 선택된 item들의 index목록을 출력
- profit을 1에서 50사이의 정수, weight을 1에서 10사이의 정수로 무작위 선택
- Capacity는 전체 weight 합의 60%를 반올림 한 값
- profit/weight 값이 큰 것 순으로 sorting 후 실행

참고자료

· 알고리즘(Neapolitan / Naimipour , 사이텍미디어)