Backtracking 기반의 0-1 Knapsack 알고리즘 소스 + 성능분석

소개글

Backtracking 기반의 0-1 Knapsack 알고리즘 소스 + 성능분석에 대한 보고서 자료입니다.

목차

서론

관련연구

알고리즘 분석

실험 및 분석

결론 및 고찰

<부록>
소스코드

본문내용

h>
#define TRUE 1
#define FALSE 0
#define YES 1
#define NO 0
#define N 100000
//#define TOTAL_W 16
#define index int
int TOTAL_W;
int maxprofit = 0;
int numbest;
int bestset[N];
// 실험 1
//int p[N] = {50, 10, 40, 30};
//int w[N] = {10, 5, 2, 5};
// 실험 2
//int p[N] = {20, 30, 35, 12, 3};
//int w[N] = {2, 5, 7, 3, 1};
// 실험 3
int p[N];
int w[N];
int include[N];
void knapsack(index i, int profit, int weight) {
int promising(index, int, int);
int temp = 0;
// 최고의 값인 경우
if(weight <= TOTAL_W && profit >= maxprofit) {
// numbest를 고려한 아이템의 개수로 놓고, bestset을 이 해 답으로 놓는다.
maxprofit = (int)profit;
numbest = i;
bestset[i] = include[i];
//printf("%d %d\n", profit, weight);
}
if(temp = promising(i, profit, weight)) {
// w[i] 포함
include[i] = YES;
knapsack(i + 1, profit + p[i], weight + w[i]);
// w[i] 미포함
include[i] = NO;
knapsack(i + 1, profit, weight);
}
}
int promising(index i, int profit, int weight)
{
index j, k;
int totweight;
int bound = 0;
// 자식마디로 확장할 수 있을 때만 마디는 유망하다.
// 자식마디에 쓸 공간이 남아 있어야 한다.
if(weight >= TOTAL_W)
return FALSE;
else {
j = i;
bound = profit;
totweight = weight;
// 가능한 한 많은 아이템을 취한다.
while(j < N && totweight + w[j] <= TOTAL_W) {
totweight = totweight + w[j];
bound = bound + p[j];
j++;
}
k = j;
if(k < N)
bound = bound + (TOTAL_W - totweight) * p[k] / w[k];
return bound > maxprofit;
}
}
main()
{
int i, j, temp;
int sumWeight = 0;
FILE *in;
double ticksPerSec, diff;
struct tms start, end;
clock_t startTick, endTick, userTick, systemTick;
ticksPerSec = (double)sysconf(_SC_CLK_TCK);
in = fopen("in.txt", "w");
for(i = 0; i < N; i++) {
// profit 1~50 사이로
p[i] = (rand() % 50) + 1;
// weight 1~50 사이로
w[i] = (rand() % 10) + 1;
sumWeight += w[i];
fprintf(in, "%d %d\n", p[i], w[i]);
}
TOTAL_W = sumWeight * 0.6;
// 아이템을 가격대 무게 비율로 내림차순 정렬
for(i = 0; i < N - 1; i++) {
for(j = i + 1; j < N; j++) {
if(p[i] / w[i] < p[j] / w[j]) {
temp = p[i];
p[i] = p[j];
p[j] = temp;
temp = w[i];
w[i] = w[j];
w[j] = temp;
}
}
}
//printf("bound weight\n");
// 시간측정 시작
startTick = times(&start);
// knapsack 알고리즘 실행
knapsack(0, 0, 0);
// 시간측정 종료
endTick = times(&end);
diff = (double)(endTick - startTick) / ticksPerSec;
printf("%f\n", diff);
// 최대값 출력
//printf("최대값 : %d\n", maxprofit);
}

키워드

알고리즘,   algorithm,   knapsack,   backtracking,   백트랙킹,   0-1