[공학기술]0-1 knapsack 문제에 대한 Backtracking과 Branch-and-Bound 알고리즘의 실행시간 비교

소개글

되추적이란 어떤 마디의 유망성을 점검한 후, 유망하지 않다고 판정이 되면 그 마디의 부모마디(parent)로 돌아가서(backtrack) 다음 후손마디에 대한 검색을 계속하게 되는 절차이다.

목차

1. 제목
2. 서론
3. Backtracking 알고리즘을 적용한 0-1 Knapsack (소스코드, 결과)
4. Branch-and-Bound 알고리즘을 적용한 0-1 Knapsack (소스코드, 결과)
5. 아이템 개수에 따른 실행시간 증가 추세 및 두 알고리즘의 비교 및 결론
6. 참고자료

본문내용

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>

#define NumOfItem 5 //아이템 개수+1
enum {FALSE, TRUE}; //FALSE = 0, TRUE = 1

struct Item{
int p;
int w;
float value; //value = profit/weight
} item[NumOfItem]; //아이템들의 profit와 weight를 구조체로 선언

int numbest = 0; //고려한 아이템의 개수
int maxprofit = 0; //최대 값어치
int W = 16;
int bestset[NumOfItem], include[NumOfItem];
int y[NumOfItem]; //노드의 값을 출력하기 위해 각 노드별로 배열에 저장


void knapsack(int, int, int); //배낭채우기
int promising(int, int, int); //자식마디로 팽창해야 할지를 결정

int main(){
int i,temp=0;
int profit, weight, index;

item[1].p = 40; item[1].w = 2; item[1].value = 20;
item[2].p = 30; item[2].w = 5; item[2].value = 6;
item[3].p = 50; item[3].w = 10; item[3].value = 5;
item[4].p = 10; item[4].w = 5; item[4].value = 2;

// 노드의 (x, y)에서 y값을 초기화
for( i=0 ; i<NumOfItem ; i++ ){
if( i == 0 ) y[i] = 0;
else y[i] = 1;
}

참고 자료

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