Azza's Blog

아이디어는

C-1 을 만드는 데 필요한 동전 갯수에 1원짜리 동전 하나를 더한 경우와

(C - 임의의 동전 가치) 를 만드는 데 필요한 동전 갯수 + 임의의 동전 1개인 경우를 비교해서

적은 쪽을 택하는 것.

점화식은 다음과 같다

M[C] = Change C 를 만들 때 사용하는 가장 적은 동전의 수 라고 했을 때,

M[C] = MIN( M[C-1]+1, M[C - V[j]]+1)        // 단, j = 1 ... N 이고 C >= V[j]

void minimum_coins() {
    int i, j;

    M[0] = 0;
    for(i = 1; i <= CHANGE; i++) {
        for(j = 0; j < NUM_OF_TYPES; j++) {
            if(i >= V[j])
                M[i] = MIN(M[i-1]+1, M[i-V[j]]+1);
        }
    }

}

아이디어는

D[i][j] = i 번째까지의 동전을 가지고 j 금액을 만드는 경우의 수

i-1 번째까지의 동전을 가지고 j 금액을 만드는 경우의 수에, i 번째 동전이 추가된 경우는 ==> ?

( j - i 번째 동전의 가치 * k) 의 경우의 수를 모두 더하는 것.

즉, 새로운 동전의 가치가 5 라면, { 5 }, { 55 }, { 555 } ... 가 추가되는 경우의 수를 모두 더하는 것.

점화식을 보자면, (여기서 동전의 타입의 넘버링은 0th ~ (N-1)th 까지로 생각한다)

( i == 0 인 경우 )

D[i][j] = 1    

( 아니라면 )

D[i][j] = D[i-1][j] + SUM(D[i-1][j-V[i]*k)        // k 는 자연수이고. j >= V[i]*k 인 경우.

void ways_to_make_change() {
    int i, j, k;

    for(i = 0; i < NUM_OF_TYPES; i++) {
        for(j = 0; j <= CHANGE; j++) {
            if(i == 0) {
                D[i][j] = 1;
            } else {
                D[i][j] = D[i-1][j];
                for(k = 1; j >= V[i]*k; k++) {
                    D[i][j] += D[i-1][j-V[i]*k];
                }
            }
        }
    }
}

내가 생각한 아이디어는 다음과 같다.

S[i][j] = A(i) ... A(j) 까지의 합이라고 할 때,

( j = i 인 경우) S[i][j] = A[j];

( j > i 인 경우 ) S[i][j] = S[i][j-1] + A[j];

요렇게 하면 따로이 Sum 루틴이 필요 없이,

착착 계산되어 진다는 거...

이 계산하면서 Max Sum 값을 체크하여 기억해 두면 OK.

간단하게 핵심 루틴만 적어본다면...

void find_max_sum() {
    int c, i, j;
    int max_s = 0, max_e = 0, max_sum = INT_MIN;


    for(c = 1; c <= NUM_OF_NUMBERS; c++) {   // subsequence count
        for(i = 0; i < NUM_OF_NUMBERS-c+1; i++) {   // start position
            j = i+c-1;
            if(c == 1) {
                S[i][j] = A[j];
            } else {
                S[i][j] = S[i][j-1] + A[j];
            }
            if(S[i][j] > max_sum) {
                max_sum = S[i][j];
                max_s = i;
                max_e = j;
            }
        }
    }
}

(2012.8.30 수정)

이 문제를 해결하는 좋은 알고리즘이 있었다.

Kadane's Algorithm 이다. (지나가던 과객님께 감사드립니다 (__) )

아이디어는 다음과 같은 것이다.

MaxSum(N) : N번째 원소가 포함된 Max Contiguous Subsequent Sum

MaxSum(N) : Max( MaxSum(N-1), A(N) )

( MaxSum은 굳이 배열이 아니라 그냥 변수 하나로 써도 된다 )

MaxSoFar : 계속 계산해 가던 MaxSum 들 중 최대값.

위키피디아의 파이썬 소스를 적어보면, 아래와 같다.

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

(C++ 코드)

int i = 0, j = 0, k = 0;
int MaxEnd, MaxSoFar;

MaxSoFar = MaxEnd = A[0];
for(int n = 1; n < NUM_OF_NUMBERS; n++) {
    MaxEnd = MAX(MaxEnd + A[n], A[n]);
    if(MaxEnd == A[n])
        k = n;
    if(MaxEnd > MaxSoFar) {
        MaxSoFar = MaxEnd;
        i = k;
        j = n;
    }
}

/*
 * 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개로도 구현이 가능하다.