我是用手机测试的~编译器C4droid~也许是版本不同问题

程序执行是个死东西，算法不变（ai算法除外）、给的输入相同，程序就永远给出相同的结果。
错的就是错的，在什么版本的编译器下都是错的。经检查，我得出正确结果的代码和38楼代码略有不同，将显示符号“|”和显示数字的代码顺序对调一下就可，如下：
for(i=j=0;i<n;i++)
        {
            printf("%2d ",a[i]);
            if(i==c[j])
            {
                printf("|");
                j++;
            }
        }

修改为：
for(i=j=0;i<n;i++)
        {
            if(i==c[j])
            {
                printf("|");
                j++;
            }
            printf("%2d ",a[i]);
        }

这个逻辑问题当然任何正常的编译器都不能得出期望的结果啦~

或许是我敏感了~因为我发现了我用的C4droid除了不支持中文外~对于memset函数不能完全清零~有些处理细节还是和别的编译器有一点出入的~所以才往这方面想去了~~

以下程序应用动态规划进行优化
#include <stdio.h>
#include<stdlib.h>
#include <assert.h>
#include <string.h>

int lineSave[100][100];
int main(void)
{//fun

 int n ;
 int k ;
  int i,j,v ;
  int blockLen,blockNumber;
  int sum,weight,index;
  int *data;
 
  int getRangeWeight(int *data,int start,int end);
 
   scanf("%d%d", &n, &k);
    assert(n >= k);
data=(int*)malloc(n*4);
blockLen=k+2;
blockNumber=n-k+1;

for (i = 0; i < n; ++i)  scanf("%d", data+i);

for(i=0;i<k;++i)  lineSave[0][i]=i;

  lineSave[0][k]=n;
lineSave[0][k+1]=0;
for(i=1;i<blockNumber;i++)
    memcpy(&lineSave[i][0],lineSave,blockLen*4);

for(i=k-1;i>0;--i)
  
  {//for01
    for(j=0;j<blockNumber;++j)
    {//for02
       lineSave[j][i]+=j;
       lineSave[j][blockLen-1]+=getRangeWeight(data,lineSave[j][i],lineSave[j][i+1]);

       for(v=j+1;v<blockNumber;++v)
       {//for03
      
        if((weight=lineSave[v][blockLen-1]+getRangeWeight(data,lineSave[j][i],lineSave[v][i+1]))<lineSave[j][blockLen-1])
        {
              lineSave[j][blockLen-1]=weight;
             memcpy(&lineSave[j][i+1],&lineSave[v][i+1],(k-i-1)*4);
         }
        }//for03
      }//for02
    }//for01

 weight=0x7fffffff;
 for(i=0;i<blockNumber-1;++i)
 {
    int w;
    w=getRangeWeight(data,0,lineSave[i][1])+lineSave[i][k+1];
    if(w<weight)
    {
      weight=w;
      index=i;
   
    }

 }
sum=weight*2;
for(i=0;i<n;++i)
sum+=data[i]*data[i];

printf("%d\n",sum);
j=0;
 printf("%d",data[0]);
   ++j;
for(i=1;i<k;++i)
{//for01
   for(;j<lineSave[index][i];++j)
        printf(" %d",data[j]);
  
 printf("|%d",data[j]);
++j;
}//for01
   for(;j<lineSave[index][k];++j)
        printf(" %d",data[j]);
printf("\n");

free(data);
return 0;
}//fun


int getRangeWeight(int *data,int start,int end)
{
int weight=0,i,j;
if(end-start<=1) return 0;
for(i=start;i<end-1;++i)
   for(j=i+1;j<end;++j)
      weight+=data[i]*data[j];
return weight;
}

虽然我没有对这个程序进行全面测试~不过感觉应该能找到一种可行的优化方法~感觉这个程序的优化是有可能成立的~当然要把可能变成一定还需要通过全面测试和一定的推理证明~

我对优化的理解就是尽量减少遍历次数~减少遍历次数就意味着不是对所有状态进行搜索~这样意味着要保证不搜索的状态必定不是最优解~这就意味着要证明不被搜索的状态不是最优解~其中要涉及到数学证明~所以优化就是直接利用证明结果而省略了证明过程~难点就是要找到n的平方这个约束条件是否有或者有怎样的线性约束关系~
如果存在线性约束关系则可以进行剪枝~如果没有则很难进行优化了~这题不多不少都可以找到一些线性约束关系的~只不过是线性相关性强弱问题~

感觉如果把n的平方换成求划分sin(n)的和就没啥线性约束关系了~这还是要老老实实搜索吧~

证明一元线性相关不难~问题是多元的线性关系~如果能够证明n+1的最优解的两个相邻划分标记不被n的最优解的任意一个划分的开区间包含就可以从非多项式运算级别优化到多项式运算级别了~

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

 

#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编辑过]

还在研究这题啊~很久都没有弄算法了~~

四层循环啊~~~时间估计为复杂度为0(n^4)~~~~~~~~~~~

四层循环 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)