[DP] Knapsack 알고리즘 - C언어

Knapsack 알고리즘 - C언어

---

1. Knapsack 알고리즘

2. 코드 구현

 

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

---

1. Knapsack 알고리즘

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

 

해당 포스팅에서는 DP를 다뤄보겠습니다.

 

2. 코드 구현

- 전체 코드

#include <stdio.h>
 
int max(int a, int b) {
    return (a > b) ? a : b;
}
 
int knapSack(int W, int wt[], int val[], int n) {
    int i, w;
    int K[n + 1][W + 1];
   
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0){
            	K[i][w] = 0;
        	} else if (wt[i - 1] <= w){
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
        	} else {
                K[i][w] = K[i - 1][w];
        	}
        }
    }
   
    return K[n][W];
}
 
int main() {
    int val[] = {10, 40, 30, 50};
    int wt[] = {5, 4, 6, 3};
    int W = 10;
    int n = 4;
   
    printf("최대 가치: %d\n", knapSack(W, wt, val, n));
    return 0;
}

 

- DP 핵심 코드 설명

else if (wt[i - 1] <= w) {
    K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
}

 

1. 현재 물건을 넣을 경우 val[i-1] + K[i-1][w - wt[i-1]]

현재 물건의 가치 val[i-1]를 더한 후, 남은 무게 w - wt[i-1]에서 얻을 수 있는 최대 가치 K[i-1][w - wt[i-1]]를 더합니다.

 

2. 현재 물건을 넣지 않을 경우 K[i-1][w]

이전 아이템까지 고려한 상태를 그대로 유지합니다.

 

3. 최적의 해 선택

위의 두 가지 경우 중 더 큰 값을 최적의 해로 선택합니다.

---

참고 사이트

[알고리즘 정리] 배낭 문제(Knapsack Problem)

 

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

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