/*
* knapsack.cpp
*
* Created on: 2012. 7. 31.
* Author: jiwoong.yoo
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#define NUM_OF_ITEMS 5
#define MAX_VALUE 20
#define MAX_WEIGHT 10
#define MAX_BOUND 3
#define KNAPSACK_CAPACITY 15
#define MAX(a,b) (((a)>(b))?(a):(b))
int V[NUM_OF_ITEMS];
int W[NUM_OF_ITEMS];
int B[NUM_OF_ITEMS];
int D[NUM_OF_ITEMS+1][KNAPSACK_CAPACITY+1];
void gen_data();
void knapsack(int type);
int main() {
gen_data();
knapsack(0);
knapsack(1);
knapsack(2);
return 0;
}
// type: 0: 0-1, 1: Bounded, others: Unbounded
void knapsack(int type) {
int n, c, b, max_b;
for(c = 0; c <= KNAPSACK_CAPACITY; c++)
D[0][c] = 0;
for(n = 0; n < NUM_OF_ITEMS; n++) {
for(c = 1; c <= KNAPSACK_CAPACITY; c++) {
// Set bound
if(type == 0)
max_b = 1;
else if(type == 1)
max_b = B[n];
else
max_b = INT_MAX;
for(b = 1; b <= max_b && W[n]*b <= KNAPSACK_CAPACITY; b++) {
if(n == 0) {
if(c >= W[n]*b) {
D[n][c] = V[n]*b;
} else {
D[n][c] = 0;
}
} else {
if(c >= W[n]*b) {
D[n][c] = MAX(D[n-1][c], D[n-1][c-W[n]*b]+V[n]*b);
} else {
D[n][c] = D[n-1][c];
}
}
}
}
}
printf("[Type:%d][Capacity %d] Max Value = %d\n",
type, KNAPSACK_CAPACITY, D[NUM_OF_ITEMS-1][KNAPSACK_CAPACITY]);
}
void gen_data() {
srand(time(0));
for(int i = 0; i < NUM_OF_ITEMS; i++) {
V[i] = rand() % MAX_VALUE + 1;
W[i] = rand() % MAX_WEIGHT + 1;
B[i] = rand() % MAX_BOUND + 1;
printf("[%2d]th item: V = %2d, W = %2d, B = %2d\n",
i, V[i], W[i], B[i]);
}
printf("========================================\n");
}
Dynamic Programming도 문제를 더 작은 문제로 나눠서 해결하는 방법이다.
Knapsack Problem은 다음과 같이 문제를 나눠서 해결한다.
D[n][c] : c 크기의 배낭에 n 번째까지의 아이템을 넣는다고 했을 때, Max Value 값.
D[n][c] : (c >= W[n]*b 인 경우)
MAX(D[n-1][c], D[n-1][c-W[n]*b]+V[n]*b)
(아닌경우)
D[n-1][c];
(단, x < 0 이면, D[x] = 0)
머, 이 정도로 정리가 가능하겠다. 어쨌거나 이해하기 어렵긴 마찬가지.
머리가 정말 좋은 사람이 아니라면, 한참을 고민을 해야 어렴풋이 감이 잡히리라 생각한다.
어쨌거나 나의 생각도 정리할 겸 설명을 해보면,
일단 N 개의 아이템에서 N 번째 아이템을 제외하고,
가방에 넣었을 때의 Optimal Solution을 D[n-1][c] 라고 생각한다.
(물론 이건 밑에서 부터 구해와야 하는 값이다. 생각 자체는 저런식으로 한다는 거다.)
D[n-1][c] 상황에서 N 번째 아이템이 '짠'하고 등장했을 때,
N 번째 아이템을 넣지 않았을 때의 Value 값과,
N 번째 아이템의 Weight 만큼 제외한 Value 값에 N 번째 아이템의 Value를 더한 값을 비교해서
둘 중 큰 값을 D[n][c] 의 Max Value 로 선택하는 것이다.
(즉, 다른걸 빼고 N 번째 아이템을 넣느냐 마느냐 선택하는 것)
추가로 좀 더 이야기 하면,
Unbounded Knapsack Problem 이라면,
D는 1차원 배열로 충분하다.
나머지 2가지의 경우도 D[n]번째 계산과정까지 오면, D[n-2]이하는 필요 없으므로,
잘 작성한다면 1차원 배열 2개로도 구현이 가능하다.
