刚刚更新了18楼的代码~加入了数据倒置重新检查~这样效率又低了不过确保了正确率~问题少了不过还是有点bug~

就是那个17选10的还是取不了最小值~不过已经接近最小值了~感觉除了全部遍历外得要找到数学方法才行~

[此贴子已经被作者于2017-4-19 14:14编辑过]

凑个热闹聊几句，首先说如果用穷举法暴力解决，所有的方法总数是多少，答案应该是M-1个元素的K-1的组合，例如5个数分3组就是C(4,2)=6，总计有6种不同的方法，至于为什么是这么多，什么道理，以后再说吧，似乎知道总数对解决问题帮助不大。另外一点，如何判断两种不同组合的大小，用两种不同组合的和的大小来判断结果是不完全正确的，也就是说不同组合方式中相异组合的和大小并不能代表各自方式的大小，有点绕，举例，1:a,b|c|d  2:a|b|c,d  如果a+b>c+d,并不能代表1的结果比2的结果大，例证，1,7|3|4   1|7|3,4  1+7>4+3 然而前者平方和的结果是89，后者是99，不太准确的说应该以乘积大小来判断。至于为什么以后解释，今天先说这些吧。

K SUM

17 5         11605
17 10        6379
17 13        5615
15 3 18 3 21 7 14 2 17 9 20 2 38 4 35 6 23

18 4         41895  //42393
22 3 4 30 39 18 20 29 32 28 25 28 11 17 19 35 21 28

19 6          46561   //47723
19 13       22823
27 47 24 23 32 10 29 3 33 48 48 20 22 11 19 49 21 45 16

24 8          26971  //27591
24 13        17133
24 18        13087
27 31 9 23 37 7 7 18 32 4 8 32 41 8 11 22 22 5 21 32 7 11 33 13

[此贴子已经被作者于2017-4-20 01:05编辑过]

数据一大就会偏离标准值~找到具体原因就是那个程序的目标函数只能代表局部最优解而不一定是全局最优解~

感觉除了遍历所有组合外~还需要寻找一个恰当的目标函数才能减少遍历组合~难点还要在于目标回溯~就是找到一个局部最优解的时候还需要回溯局部最优解附近是否存在更优解~不过麻烦的是如果局部最优解和全局最优解虽然差点点~但如果组成结构偏离很远就意味着要通过大量的搜索量才能找回或者搜索不到了。

对哦~还有一个问题~负数怎么处理？~
我尝试列了个二维方阵来保存两个区间的和~不难理解正数的话数据总是在在对角线取得极小值~然后对角线两边依次增大~
但如果是负数的话方阵数据的无序性就会大大增强~意味着目标函数更容易失效~

不过实际上用一维数组和二维数组在少数据的时候差别不大~因为总区间都可以通过任意一段中间的区间和相邻两段子区间组合而成~所以只需要算第一层区间和~算中间的直接用第一层区间和减去相邻两个区间和就行了~这样计算空间和效率比是很高的~就是每次比二维数组保存多了一次减法运算~但空间分配能降低到原来的1/N~

设数据总和为sum;(0-x1)区间的和为a,(0-x2)区间的和为b则(x1,x2)区间的和为b-a~  

所以有一种感觉(感觉而已,不知有没有说错)~实际处理很多复杂的动态规划问题就像下棋一样~找到一个合理解比找到一个最优解要简单很多~因为合理解只是考虑局部最优解(贪心算法)然而全局最优解就可能要搜索所有分支~

这条题有时间再研究一下~毕竟最近数学渣更不上~要去补习了~

顺便问问有没有要求支持负数~或者拿几个含有负数的案例拿出来研究研究？~

[此贴子已经被作者于2017-4-19 23:36编辑过]

学习

是不是所取数的和正好等于平均数时平方和最小？这样的话，不断调整平均数，不断将取得的数的和与平均数比较是不是就可以得到最优解了。

试过了~就是要求所取数的和和平均数的方差~你这样说又回到原点了~

感觉策略应该是用最优解递推~先划分两份时得到最优解~然后在这个最优解的前提下调整得到划分3份时的最优解……这样如果能找到一个划分法则使在划分n份的前得到最优解的提下都可以得到n+1份的最优解问题就解决了~不然n份一起划分很难入手~

没有关于负数的例子
我刚刚想到一个方法..... 感觉又说不出个什么.... 自底向上的递推公式？
有点类似某个图...?
 求最短路径...?
求1 2 3 4 5 最小值   
高度表示k
n=5 k=3
                                                                                                                 min(5)
     k=3                                             1                                                    12                        123                   1234                 12345
     k=2                                  2,        23,        234                            3,      34,   345             4,    45                 5
     k=1                                 345     45           5                              45,     5                         5

既然每一分段K都存在最小值，那每一段最小值平方加起来应该也是最小值，
但是这样就没有动态规划的意义了......

[此贴子已经被作者于2017-4-21 12:10编辑过]

#include <stdio.h>
#include<stdlib.h>
#include <assert.h>
#include <string.h>
/*
9 5
7 11 12 5 3 20 6 5 2
 7  11 | 12 | 5  3 | 20 | 6  5  2
 ~/test # ./tests
9 7
7 11 12 5 3 20 6 5 2
 7 | 11 | 12 | 5  3 | 20 | 6 | 5  2
 ~/test # ./tests
9 3
7 11 12 5 3 20 6 5 2
 7  11 | 12  5  3 | 20  6  5  2
*/
int main(void)
{//fun

 int n ;
 int k ;
  int i ;
  int sum,weight,w;
  int *data, *line,*lineSave;
  int getNextComb(int m,int r,int *p);
  int getWeight(int *,int *,int );
  int getSum(int *,int *,int );
  int myPrint(int,int *,int * ,int );
   scanf("%d%d", &n, &k);
    assert(n >= k);
data=(int*)malloc(n*4);
line=(int*)malloc((k+1)*4);//1---k-1记录data的分割线位置，0位置0，k位置n
lineSave=(int*)malloc((k+1)*4);


    for (i = 0; i < n; ++i)  scanf("%d", data+i);
   
for(i=0;i<k;++i)
{
  line[i]=i;
  lineSave[i]=i;
}

  line[k]=n;
  lineSave[k]=n;
weight=0x0fffffff;
while(getNextComb(n-1,k-1,line))
{//while01
w=getWeight(data,line,k+1);
   if(w<weight)
   {//if01
     weight=w;
     memcpy(lineSave,line,(k+1)*4);
    }//if01
}//while01

sum=getSum(data,lineSave,k+1);
myPrint(sum,data,lineSave,k+1);
free(data);
free(line);
free(lineSave);
return 0;
}//fun

int getNextComb(int m,int r,int *p)
{//fun
    int i,j;
    i=r ;
    while(p[i]==m-r+i && i>=1) --i;
    if(i<1) return 0;
    p[i]+=1;
    for(j=i+1;j<=r;++j)
        p[j]=p[j-1]+1;
    return 1;

}//fun

int getWeight(int *data,int *line ,int r)//r为line数目
{
int i,j,v,weight=0;

for(i=1;i<r;++i)
{//for01
   int s,e;
s=line[i-1];
e=line[i];
   if(e-s>1)
   for(j=s;j<e-1;++j)
      for(v=j+1;v<e;++v)
        weight+=data[j]*data[v];
  
}//for01
return weight;
}

int getSum(int *data,int *line ,int r)
{
int i,j,sum=0,m;
for(i=1;i<r;++i)
{//for01
   m=0;
   for(j=line[i-1];j<line[i];++j)
         m+=data[j];
   sum+=m*m;
}//for01
return sum;
}

int myPrint(int sum,int *data,int *line ,int r)
{
int i,j;
printf("%d\n",sum);
j=0;
 printf("%d",data[0]);
   ++j;
for(i=1;i<r-1;++i)
{//for01
   for(;j<line[i];++j)
        printf(" %d",data[j]);
  
 printf("|%d",data[j]);
++j;
}//for01
   for(;j<line[r-1];++j)
        printf(" %d",data[j]);
printf("\n");
return 0;
}

以上代码是枚举所有可能比较大小最后得到结果，这种方法效率比较低，以后再考虑优化算法吧，这种算法对负数适用。

n个整数分成k段

遍历一遍整数，找到一组相邻的组合形成的和最小的数字将它们结合。
重复上一步骤，直到剩下的数字只剩k个。

实际写代码的时候很直接我们会想到要用最小堆。具体方法  可以用n个node{一个指向它左边的node的指针;一个指向这个node区间开始的位置;一个指向这个Node区间结束的位置;一个权值表示这个区间从开始位置到结束位置所有数字的和}
每个node的权值取决于它的区间本身数字和与他左边那个区间的数字和，因此每当我们对堆内任何一个node进行组合都需要删去一个多余的堆并且重新初始化排序整个堆。整体算法复杂度为O((n-k)*logn)
/***********2017-04-24补充：由于从最小堆中弹出最小的那个node之后可以直接更新node左边的结点为{左边node的左边node指针；左边node的区间开始位置；右边node的区间结束位置；左边Node和Node自己的权值之和}

[此贴子已经被作者于2017-4-24 07:12编辑过]