贪心算法没有最优解 动态规划有最优解[

 

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <limits.h>

int solution(int*C,int first, int last) {
    int sum = 0;
    for (int n = first; n <= last; n = n + 1) {
        sum += C[n];
    }
    sum = sum * sum;
    return sum;
}

int SquareNormClustering(int*A,int n,int k){
    int**C;
    int inf  = INT_MAX;
    int *line;
    
    C = (int**)malloc(sizeof(int*)*n);
    for (int i=0; i<n; i++) {
        *(C+i) = (int*)malloc(sizeof(int)*(k+1));
    }
    
    for (int loop = 0; loop < n; loop++) {
        C[loop][1] = solution(A, 0, loop);
    }
    
    line = (int*)malloc(sizeof(int)*n);
    for (int l = 2; l <= k; l++) {
        for (int j = l - 1; j < n; j++) {
            int Min = inf;
            int Min2 = inf;
            for (int i = l - 2; i <= j - 1; i++) {
                Min2 = C[i][l - 1] + solution(A, i + 1, j);
                if (Min2 < Min) {
                    Min = Min2;
                }
            }
            C[j][l] = Min;
        }
    }
    return C[n-1][k];
}

int main(int argc, const char * argv[]) {
    
    int n,k;
    int *set;
    printf("input n and k");
    scanf("%d%d",&n,&k);
    
    set=(int*)malloc(n*4);
    printf("input %d numbers",n);
    for (int i=0; i<n; i++) {
        scanf("%d",&set[i]);
    }
    
    int min = SquareNormClustering(set,n,k);
    printf("min result is %d",min);
    
    return 0;
}

[此贴子已经被作者于2017-5-20 20:44编辑过]

四层循环 O(k*n^3)
for (int l = 2; l <= k; l++) {
      for (int j = l - 1; j < n; j++) {
         for (int i = l - 2; i <= j - 1; i++) {
                    Min2 = C[i][l - 1] + solution(A, i + 1, j);
优化是把solution全部计算出来再循环 这样就是三层循环 O(n^2 * k)