Knapsack Problem 냅색 문제
배경 혹은 필요성
예를 들어, 배낭에는 최대 4kg까지 넣을 수 있다.
물건 A~C 중 어느 것을 담아야 할까?
방법론
1. 비싼 물건 먼저 차례로 넣는다.
2. 가벼운 물건 먼저 차례로 넣는다.
3. 비싼 물건 먼저, 가벼운 물건 먼저 두 가지 방법으로 모두 해보고,
그 중 금액이 비싼 것을 선택한다.
=> 세 가지 방법 모두 틀림.
왜냐하면 문제가 아래와 같은 조건으로 주어질 경우, 잘못된 답을 고르게 되기 때문이다.
또 다른 방법론으로 Exhaustive Search가 있다.
모든 경우의 수를 다 확인해보는 방법이다.
이 방법을 사용할 경우, 지금 문제의 경우의 수는 A를 배낭에 넣고 안넣고 2가지가 가능하고,
B를 배낭에 넣고 안넣고 2가지, C를, D를,,, 해서 A~G 7개 모두 넣고 안넣고 2가지의 경우가 가능하다.
따라서 전체적으로 2^7 = 128가지의 경우의 수가 존재한다.
시간 복잡도는 O(2^n) 이다. 매우 큼!
개념
배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때,
가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제.
짐을 쪼갤 수 있는지에 따라 2가지로 나눌 수 있음.
(1) 분할가능 배낭문제(Fractional Knapsack Problem) : 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)
-> 그리디 알고리즘으로 풀 수 있음.
(2) 0-1 배낭 문제(0-1 Knapsack Problem) : 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능)
-> 동적계획법(DP)으로 풀 수 있음.
물건 개수가 몇 개인지에 따라 3가지로 나눌 수 있음. (위에서 분류한 방법에서 0-1배낭문제에 아래 3가지 종류가 포함되는 것 같기도하고)
(1) Bounded Knapsack Problem : 물건(짐)마다 최대 개수가 정해져 있어 A물건 3개, B물건 2개 ,,, 등등
(2) 0-1 Knapsack Problem : 물건마다 최대 개수는 1.
(3) Unbounded Knapsack Problem : 물건 종류(무게와 가격)만 있을 뿐 개수는 무제한으로 사용 가능.
Knapsack Problem의 사용 예시
배에 container를 실을 때, 균형과 무게의 조화가 필요하다.
천을 재단할 때, 낭비되는 천의 부분을 최소화하기 위해.
강의실 편성할 때, 고려조건은 수강인원과 강의실 수용 인원.
=> 공통점 : 자원이 일정할 때, 그 자원을 어디에 배치시킬 것인지 결정한다.
Unbounded Knapsack Problem 문제 풀이
(물건의 개수가 무한할 때)
배낭에 담을 수 있는 최대 무게는 8kg 이고, 물건들이 아래와 같은 조건으로 주어졌을 때, 최대 금액을 구해보자.
1차원 배열을 만들어서 칸을 채워나가며 정답을 찾는다.
배열의 크기는 배낭무게+1 이어야한다! 그래야 인덱스를 0~배낭무게까지 가질 수 있기때문에
이 때, 배열의 인덱스는 가방에 들어갈 수 있는 최대 무게를 뜻하고, 배열 안의 값은 최대 금액을 뜻한다.
이 때 연산량은 1+2+3+...+n = n*(n+1)/2 이므로, O(n^2)가 된다. => 사실 왜인지 모르겠음...
만약, 해당 문제에서 Exhausted search 기법을 사용한다면? 배낭의 최대 무게는 n kg 이다. <내 풀이. 틀릴 수 있음>
물건1을 0개 넣었을 때, 1개 , 2개, 3개, ..., n개(배낭이 n kg이므로 최대 n개까지 넣을 수 있음. )넣는 경우,
물건2를 0개 넣었을 때, 1개 , 2개, 3개, ..., n개 넣는 경우,
물건3을 0개 넣었을 때, 1개, 2개, 3개, ..., n개 넣는 경우 가 있고
이 모든 경우가 동시에 일어날 수 있으므로 n*n*n의 시간 복잡도를 가진다. O(n^3)
공식 :
m[c] = MAX[ vi + m[c-wi] ] ( wi<= c)
m[c] : c kg까지 무게를 넣을 수 있을 때, 최대 금액
vi : i번째 물건을 넣었을 때 얻을 수 있는 가격
m[c-wi] : i번째 물건을 넣고, 그 이후에 넣을 수 있는 무게(c-wi)에서, 최대 금액
C언어 구현코드
#include < stdio.h >
#include < stdlib.h > // malloc
#include < string > // memset
#define NUM_OF_PRODUCT 3
struct product {
int value; // 가격
int weight;
};
struct product products[NUM_OF_PRODUCT];
void initProducts() {
products[0].value = 1;
products[1].value = 4;
products[2].value = 5;
products[0].weight = 1;
products[1].weight = 2;
products[2].weight = 3;
}
int *initKnapsackTable(int _c) {
int *t = (int *)malloc(sizeof(int)*(_c + 1));
memset(t, 0, sizeof(int)*(_c + 1));
return t;
}
int findMaximumValue(int *_m, int _c) {
int _maxValue = 0;
for (int i = 0; i < NUM_OF_PRODUCT; i++) {
int new_value;
if (products[i].weight <= _c) {
new_value = products[i].value + _m[_c - products[i].weight];
if (new_value > _maxValue) {
_maxValue = new_value;
}
}
}
if (_maxValue==0) { // 물건들의 무게가 _c보다 다 커서, 넣을 수가 없음.
_maxValue = _m[_c - 1];
}
return _maxValue;
}
int main(void) {
int c = 8; // 최대 담을 수 있는 무게(배낭의 수용 무게)
int *m = 0;
initProducts(); // 각 물건의 무게, 가격 초기화
m = initKnapsackTable(c); // DP를 채울 테이블 동적 할당
m[0] = 0;
for (int i = 1; i <= c; i++) { // DP 테이블 채워나가기
m[i] = findMaximumValue(m, i);
}
printf("최대 가격은 %d\n",m[c]);
free(m);
return 0;
}
0-1 Knapsack Problem 문제 풀이
(물건의 개수가 1개일 때)
배낭에 담을 수 있는 최대 무게는 4kg 이고, 물건들이 아래와 같은 조건으로 주어졌을 때, 최대 금액을 구해보자.
