[알고리즘]배낭문제(0/1Knapsack Problem)

소개

배낭 알고리즘을 C코드로 구현한 소스와 보고서이다.

1.Knapsack problem 이란?
일명 배낭 문제라고 하는 이 알고리즘은 조합 최적화의 유명한 문제이다.
간단하게 말하면 한, 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

이 문제는 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는 경우 두 가지로 나눌 수 있는데 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제 (Fractional Knapsack Problem), 짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부른다.

2.함수 설명

knapsack() : 최대이익을 계산하여 물건들의 최적조합을 찾는 함수.

-중량을 초과하지 않고 현재의 이익이 이전에 구한 최대이익보다 크다면 현재의 이익이 최대이익이 되고 현재 물건들의 조합은 최적의 조합이 된다.
-현재의 물건이 유망한가를 검사하여 유망하면 그 다음 물건을 포함 했을 때와 안했을 때를 검사한다.
-다음 물건에 관하여 knapsack()함수를 재귀적으로 호출하여 최종 솔루션을 구한다.

promising() : bound값과 최대 이익값을 비교하여 그 물건에 대해 유망한지 아닌지 판별하는함수

-중량을 초과 하지 않고 현 상태에서 구한 bound값이 이전에 구한 maxprofit 보다 크다면 유망하다.

3.프로그램 소스
#include

#define MAX 501
int knapsack(int i,int profit,int weight);
int promising(int i,int profit,int weight);


int n,w;
float knap[MAX][4];
float temp[MAX][4];
int include[MAX];
int set[MAX];

int i,numbest;
float t1,t2,t3,t4;
int profit=0,weight=0,maxprofit=0,totweight=0;
float ww=0;
float pp=0;

컴파일 실행환경

Visual Studio 2010

참고자료

· Algorithm Design