- Review
냅색 문제는 물건 개수에 따라 3가지 종류가 있다.
1) Unbounded Knapsack Problem : 물건의 개수가 무제한일 때
2) 0-1 Knapsack Problem : 물건의 개수가 1개뿐일 때 ( 각 종류의 물건을 한 번만 사용할 수 있다. )
3) Bounded Knapsack Problem : 물건의 개수가 제한적일 때 ( A물건은 3개, B물건은 5개, ... )
1번 Unbounded Knapsack Problem은 이전 게시물에서 작성했고
이번에는 0-1 Knapsack Problem에 대해 공부할 것이다.
- 예제 문제
Q. 배낭에 담을 수 있는 물건의 종류와 무게, 가격이 다음과 같다고 가정할 때,
배낭 최대 수용 무게 4kg에 담을 수 있는 최대 금액은?
0-1 Knapsack Problem 의 풀이법
=> 2차원 배열 Dynamic Programming ( 점차적으로 늘려가며 찾는다. )
DP Table : m
행 : 배낭에 넣을 수 있는 물건
ex ) i행 : A부터 i번째 물건까지 넣을 수 있다고 가정하였을 때...
열 : 배낭 수용 kg
DP Table을 채울 때
m[E,1] 계산값
물건 E의 무게가 > 배낭 수용 무게 보다 클 경우, 계산값은 0,
m[E,1] = m[D,1]
DP table을 일일이 채운 공식들
다 채울 경우 DP Table
!정리!
DP 2차원 배열
m[r][c]
r : r번째 물건까지 채울 수 있음.
c : 배낭에 담을 수 있는 최대 무게
수도코드
1) if wi > c, m[i-1,c] // 배낭을 다 비워도 wi무게를 넣을 수 없는 경우
-> i번째 물건은 배낭의 최대 수용 무게를 넘기 때문에,
i번째 물건을 제외하고, i-1번째 물건까지 채웠을 때의 최대 무게(m[i-1,c])가 최대 value가 된다.
2) if wi <= c, MAX( m[i-1,c], vi+m[i-1,c-wi] ) // wi무게를 배낭에 넣을 수 있는 경우
-> 물건 i를 안넣는 경우와
물건 i를 넣는 경우 중, 가격이 높은 것으로 MAX
(-> 물건 i를 넣는 경우 : vi+m[i-1,c-wi] // 물건 i의 가격 + 물건 i를 제외하고 나머지 배낭을 채웠을 때의 최대값 )
- C언어 구현코드
#include < stdio.h >
#include < stdlib.h > // malloc
#include < string.h > // memset
#define NUM_OF_PRODUCT 7
struct product {
int value; // 가격
int weight;
};
struct product products[NUM_OF_PRODUCT];
void initProducts() {
products[0].value = 1;
products[1].value = 1;
products[2].value = 1;
products[3].value = 1;
products[4].value = 3;
products[5].value = 3;
products[6].value = 5;
products[0].weight = 1;
products[1].weight = 1;
products[2].weight = 1;
products[3].weight = 1;
products[4].weight = 2;
products[5].weight = 2;
products[6].weight = 4;
}
int **initKnapsack2DTable(int _numP, int _c) {
int **_m = (int **)malloc(sizeof(int*)*(_numP+1));
for (int i = 0; i <= _numP; i++) {
_m[i] = (int *)malloc(sizeof(int)*(_c + 1));
memset(_m[i], 0, sizeof(int)*(_c + 1));
}
return _m;
}
int findMaximumValuefor2DTable(int **_m, int _r, int _c) {
int new_value=0;
if ( products[_r].weight <= _c) {
new_value = products[_r].value + _m[_r-1][ _c-products[_r].weight ];
}
// _r번째 물건을 넣었을 때와
// 넣지 않았을 때
// 중에서 큰 값을 return
if (_m[_r-1][_c] > new_value) {
return _m[_r-1][_c];
}
else {
return new_value;
}
}
int main(void) {
int capacity = 3; // 최대 담을 수 있는 무게 (배낭의 수용 무게)
int **m = 0; // DP Table - 2차원 배열
initProducts(); // 물건(짐)의 종류별 무게, 가격 초기화
m = initKnapsack2DTable(NUM_OF_PRODUCT, capacity); // DP Table 2차원 배열 동적 할당
// DP Table 채우기
for (int r = 0; r <= NUM_OF_PRODUCT; r++) {
for (int c = 0; c <= capacity; c++) {
if (r==0 || c==0) { // 물건 아무것도 없을 때, (r=0)
// 배낭 최대 수용무게가 0일 때 (c=0)
m[r][c] = 0;
continue;
}
m[r][c] = findMaximumValuefor2DTable(m, r, c);
}
}
printf("최대 가치는 %d\n",m[NUM_OF_PRODUCT][capacity]);
return 0;
}
- 응용
Q. 각 물건들을 몇 개씩 넣는 것을 알기 위해서는?
다음과 같은 문제가 주어졌을 때, 4kg배낭
아래와 같은 수도코드로 문제를 해결해 나갈 수 있다.
물건의 개수가 1개라고 하였을 때만 이 수도코드가 적용된다. (0-1 Knapsack Problem)
while(1)
{
if( m[r][c] ==0) // 탈출 조건
break;
if m[r][c] == m[r-1][c]
=> r번째 물건을 배낭에 넣지 않은 것임
r=r-1;
else m[r][c]!=m[r-1][c]
=> r번째 물건을 배낭에 넣은 것임
r=r-1;
c=c-r의 무게;
}
위의 수도 코드를 적용하면 문제를 풀어나가면,
Q. 물건 A,B,C,D가 모두 있을 때 4KG를 채운 물건은? (m[D][4])
=> D, C, B, A
Q. 물건 A,B,C,D,E,F,G가 모두 있을 때 4KG를 채운 물건은? (m[G][4])
=> F, E
Q. 물건 A,B,C,D,E,F가 모두 있을 때 3KG를 채운 물건은? (m[F][3])
=> E, A
( 아래 종이에서 이 문제는 풀이를 적다가 끊겼는데
마지막은 m[A][1] != m[X][1] -> A o 이다.)
