/ C

알고리즘 정복하기 with C (6) The napsack Proplem

알고리즘 정복하기 with C (6) The napsack Proplem

직접 코딩하면서 알고리즘 공부하기

개요

자료구조와 알고리즘은 프로그램을 구성하는 가장 핵심적인 요소입니다. 프로그램 개발을 집을 짓는 것에 비유한다면 흙이나 모래, 시멘트, 목재와 같은 자재들이 바로 ‘자료구조’에 해당되고, 이러한 자재들을 이용해서 집을 짓는 것이 ‘알고리즘’에 해당됩니다. 알고리즘은 가장 기본적이고 중요한 부분이기 때문에 복습하는 겸해서 직접 여러가지 알고리즘을 코딩하면서 공부하기로 했습니다.

0-1 Knapsack Proplem

Knapsack Problem, 배낭 문제는 조합 최적하의 유명한 문제로 도둑이 물건을 훔칠때 무게의 한도가 정해져 있는 배낭에 가치와 무게가 할당된 아이템들로 최대한 큰 가치를 얻을 수 있도록 채우는 방법을 찾는 문제입니다. 이 알고리즘에는 특히 여러 풀이법이 있는데, 이번 글에서는 깊이 우선 방식인 Backtracking 및 Branch-and-Bound 방법을 이용하여 직접 구현해보겠습니다.

구현 방법들

  1. 아이템을 쪼갤 수 있을 때
    • Greedy Approach 방법으로 해결 가능하다. => 가장 비싼 아이템을 넣다가 마지막에 싼 아이템을 쪼개서 넣기 때문
  2. 아이템을 쪼갤 수 없을 때
    • DP, Backtracking, Branch-and-Bound 방식으로 해결 가능하다.
    • 크게 깊이 우선 탐색, 너비 우선 탐색, 최선 우선 탐색 방법으로 구현할 수 있다.

이번 글에서는 깊이 우선 탐색 방식으로 알고리즘을 구현합니다. 깊이 우선 탐색은 기본적으로 Backtracking 방식으로 해결하나 Branch-and-Bound 와도 다르지 않습니다.

The 0-1 Knapsack Problem pseudo code

The 0-1 Knapsack Problem 의 pseudo code

  1. knapsack pseudo code 
    void knapsack(index i, int profit, int weight) {
 if(weight <= W && profit > maxprofit) {
     maxprofit = profit;
     numbest = i;
     bestset = include;
 }
	
 if(promisint(i)) {
     include[i+1] = "YES";
     knapsack(i+1, profit+p[i+1], weight+w[i+1]);
     include[i+1] = "NO";
     knapsack(i+1, profit, weight);
 }
}
  2. promising pseudo code 
    bool paromising(index i) {
 index j, k;
 int totweight;
 float bound;
	
 if(weight >= W)	return FALSE;
 else {
     j = i+1;
     bound = profit;
     totweight = weight;
     while((j <= n) && (totweight + w[j] <= W)) {
         totweight = totweight = w[j];
         bound = bound + p[j];
         j++;
     }
     k = j;
     if(k <= n)	bound = bound + (W - totweight) * p[k] / w[k];
		
     return bound > maxprofit;
 }
}

The 0-1 Knapsack Problem 시간 복잡도

Backtracking 방식으로 푼 알고리즘은 시간 복잡도를 구하기 힘들다. Knapsack의 가장 최악의 방식은 2^n 이지만 실제로는 훨씬 성능이 좋을 것이다. 이러한 알고리즘의 성능을 분석하기 위해 Monte Carlo 기법이 제안되었고 이를 통해 일반적으로 Backtracking 알고리즘이 DP 보다 빠르다는 것을 입증하였다.

The 0-1 Knapsack Problem 구현

입력데이터

소스코드

#include <stdio.h>
#include <stdbool.h>
#define N 10

int W = 10;
int n = 4;
int numbest = 0, maxprofit = 0;
int w[N] = { 0 };
int p[N] = { 0 };
int include[N + 1] = { 0 };
int bestset[N + 1] = { 0 };

void knapsack(int i, int profit, int weight);
bool promising(int i, int profit, int weight);

int main()
{
    for (int i = 1; i <= n; i++) {
        printf("item%d Price : ", i);
        scanf_s("%d", &p[i]);
        printf("item%d Weight : ", i);
        scanf_s("%d", &w[i]);
    }

    knapsack(0, 0, 0);

    printf("\nprofit = %d\n", maxprofit);

    for (int i = 1; i <= n; i++)
        printf("%d ", bestset[i]);

    return 0;
}

void knapsack(int i, int profit, int weight)
{
    int j, k;
    if (weight <= W && profit > maxprofit) {
        maxprofit = profit;
        numbest = i;

        for (j = 1; j <= n; j++)
            bestset[j] = include[j];
    }

    if (promising(i, profit, weight)) {
        include[i + 1] = 1;
        knapsack(i + 1, profit + p[i + 1], weight + w[i + 1]);
        include[i + 1] = 0;
        knapsack(i + 1, profit, weight);
    }
}

bool promising(int i, int profit, int weight)
{
    int j, k, totweight;
    float bound;

    if (weight >= W)                
        return false;
    else {      
        j = i + 1;
        bound = (float)profit;
        totweight = weight;

        while (j <= n && totweight + w[j] <= W) {
            totweight = totweight + w[j];
            bound = bound + p[j];
            j++;
        }

        k = j;
        if (k <= n)
            bound += (W - totweight) * (float)p[k] / w[k];        

        return (bound > maxprofit);
    }
}

결과

The 0-1 Knapsack Problem과 출력을 구현했습니다. 결과가 잘 나옵니다.

알고리즘 진행 과정 손계산

알고리즘의 진행과정을 직접 계산하여 결과를 비교해보았습니다. 결과가 동일하게 나옵니다.