이전에 Combination 함수는

최적화 문제를 푼것이 아니라 실제 답을 계산 하도록 한것이다.

만약 실제 값 출력하지 않는다면 parent 를 바로 이전 것만 알면된다. 초기 값은 0

/**

* Combination Ver.2

*/

#define N 4

#define R 2

void comb2(int parent,int depth){

    if(depth==R-1){

        return;

    }

    for(int i=parent+1;i<N;i++){

        comb2(i,depth+1);

    }

}

int main(){

    for(int i=0;i<N;i++){

        comb2(i,0);

    }

}

동적 계획법에서 필요로 되는

reference transparency 및 최적 부분 조건이 성립해야한다.

최적 부분 조건이 성립하도록 점화식을 만들어야한다.

Quantization (Need Improv.) 버전은 이부분을 고려하지 않은 알고리즘으로 보임.

/**

* Quantization => k-mean?

*/

//#define N 10

//int input[N]={3,3,3,1,2,3,2,2,2,1};

#define S 34

#define N 36

int input[N]={1,744,755,4,897,902,890,6,777,1,744,755,4,897,902,890,6,777,1,744,755,4,897,902,890,6,777,1,744,755,4,897,902,890,6,777};

int pow2(int n){

    return n*n;

}

int minError(int s, int e){

    if(s==e){

        return 0;

    }

    bool oneNumber = true;

    for(int i=s;i<e;i++){

        if(input[i]!=input[i+1]){

            oneNumber =false;

            break;

        }

    }

    if(oneNumber){

        return 0;

    }

    float mean = 0;

    for(int i=s;i<=e;i++){

        mean +=input[i];

    }

    mean = (mean/(float)((e-s)+1.0f));

    mean +=0.5f;

    int error=0;

    for(int i=s;i<=e;i++){

        error += pow2((int)mean-input[i]);

    }

    return error;

}

void sort(){

    for(int i=0;i<N;i++){

        for(int j=0;j<=i;j++){

            if(input[j] > input[i]){

                int t = input[j];

                input[j] = input[i];

                input[i]=t;

            }

        }

    }

}

int parent[S];

//minError(s,e) 의 s,e 가 무엇이 되어야 최소가 될까? s,e 는 0~N-1까지임

//0~9 S \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0개로 나누는데 가장 작은 minError 를 주는 것.

//모든 부분 조합 완전 탐색

int n=0;

int min=-1;

int minSum(int depth){

    n++;

    if(depth == S-1){

        int sum=0;

        for(int i=0;i<S-1;i++){

            sum += minError(parent[i],parent[i+1]-1);

        }

        sum+=minError(parent[depth],N-1);

        return sum;

    }

    for(int i=parent[depth]+1;i<N;i++){

        parent[depth+1]=i;

        int t=minSum(depth+1);

        if(min==-1||t<min){

            min = t;

        }

    }

    return min;

}

int main(){

    sort();

    parent[0]=0;

    printf("%d

",minSum(0));

    printf("Function %d times

",n);

    return 1;

}

#define N 5

int triangle[N][N]={

    { 6,-1,-1,-1,-1},

    { 1, 2,-1,-1,-1},

    { 3, 7, 4,-1,-1},

    { 9, 4, 1, 7,-1},

    { 2, 7, 5, 9, 4}

};

int cache[N][N];

int n=0;

int path1(int x, int y){

    n++;

    //basis

    if(x==N || y>x){return 0;}

    if(cache[x][y]!=-1){return cache[x][y];}

    int n1 = path1(x+1,y);

    int n2 = path1(x+1,y+1);

    if(n1>n2){

        return cache[x][y]=triangle[x][y]+n1;

    }else{

        return cache[x][y]=triangle[x][y]+n2;

    }

}

int main(){

    for(int i=0;i<N;i++){

        for(int j=0;j<N;j++){

            cache[i][j]=-1;

        }

    }

    printf("%d

",path1(0,0));

    printf("Function called %d times

",n);

}