[Greedy] Knanspack 알고리즘 - C언어

Knapsack 알고리즘 - C언어

---

1. Knapsack 알고리즘

2. 코드 구현

 

알고리즘 복습하기 위해 포스팅 하고 있습니다.

---

1. Knapsack 알고리즘

배낭 문제(Knapsack Problem)은 제한된 용량을 가진 가방에 여러 개의 물건을 넣을 때, 가치의 합이 최대가 되도록 하는 최적화 문제입니다. 배낭 문제의 종류에는 0/1 배낭 문제(DP)와 분할 가능 배낭 문제(그리디 알고리즘으로 해결 가능)가 있습니다.

 

해당 포스팅에서는 그리디 알고리즘를 다뤄보겠습니다.

 

2. 코드 구현

- 전체 코드

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

typedef struct Bag {
    int value;
    int weight;
    float ratio;
} Bag;

int compare(const void *a, const void *b) {
    Bag *bag1 = (Bag *)a;
    Bag *bag2 = (Bag *)b;
    
    if (bag1->ratio < bag2->ratio) {
        return 1;
    } else if (bag1->ratio > bag2->ratio) {
        return -1;
    }
    return 0;
}

float knapSack(int W, Bag bag[], int n) {
    for (int i = 0; i < n; i++) {
        bag[i].ratio = (float)bag[i].value / bag[i].weight;
    }

    qsort(bag, n, sizeof(Bag), compare);
    
    float totalValue = 0.0;
    int currentWeight = 0;
    
    for (int i = 0; i < n; i++) {
        if (currentWeight + bag[i].weight <= W) {
            currentWeight += bag[i].weight;
            totalValue += bag[i].value;
        } else {
            int remainingWeight = W - currentWeight;
            totalValue += bag[i].value * ((float)remainingWeight / bag[i].weight);
            break;
        }
    }
    
    return totalValue;
}

int main() {
    int val[] = {10, 40, 30, 50};
    int wt[] = {5, 4, 6, 3};
    int W = 10;
    int n = 4;

    Bag bag[n];

    for (int i = 0; i < n; i++) {
        bag[i].value = val[i];
        bag[i].weight = wt[i];
    }

    printf("최대 가치: %.2f\n", knapSack(W, bag, n));

    return 0;
}

 

- 그리디 핵심 코드 설명

 

1. bag[i].ratio = (float)bag[i].value / bag[i].weight;

가치/무게 비율을 계산합니다.

 

2. qsort(bag, n, sizeof(Bag), compare);

물건을 가치/무게 비율 기준으로 내림차순 정렬합니다.

비율이 높은 물건을 먼저 담고 이렇게 정렬된 배열에서 물건을 하나 씩 선택하면서 배낭에 담을 수 있는지 체크합니다.

 

3. if (currentWeight + bag[i].weight <= W)

배낭이 해당 물건을 담을 수 있는지 확인합니다.

배낭의 최대 허용 무게를 초과하지 않는다면 그대로 추가합니다.

 

4. int remainingWeight = W - currentWeight; totalValue += bag[i].value * ((float)remainingWeight / bag[i].weight);

배낭에 물건을 전체적으로 담을 수 없을 경우 일부만 담을 수 있습니다.

이때 배낭의 최대 무게(W)에서 현재 배낭에 담긴 총 무게(currentWeight)를 빼서 배낭에 남아 있는 공간의 크기(remainingWeight)를 구합니다. 그 후 전체 물건을 다 넣을 수 없다면 일부만 넣고 그에 비례한 가치만 추가합니다.

 

배낭의 최대 무게가 10kg이고, 현재 배낭에 담긴 무게가 8kg인 상황으로 가정합니다.

이때 새로운 아이템의 무게는 5kg, 아이템의 가치는 100입니다.

 

이 경우에 배낭에는 2kg가 남아있고, 아이템의 무게는 5kg이기 때문에 전부 넣을 수 없습니다.

이때 아이템의 일부만 넣고, 그에 해당하는 가치만 추가하면 됩니다.

---

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3