动态规划

[此贴子已经被作者于2018-11-21 05:15编辑过]

有一种算法不知是否可以实现~可以试试~先划分前k个数~除了最后一组每个数据先占一个单元~
然后用递归或栈储存划分状态(这样等下出栈入栈处理比较简单)~记录当前划分数据的权值~当遇到平方和较小的时候就保存状态~否则就退出当前递归状态(出栈)~
如果用比较原始简单直接了当的做法就是遍历所有划分组合状态(~就是深度搜索~不过这样会不会超时就不敢保证了)~

具体一点这题的亮点应该是如何减少分支遍历数据和离散数据的保存方法(算平方数只需要重新算变动划分的数据就行了~没必要从新算一遍)~

当然用数学思维有一种简单的算法~就是算平均值~划分数据和平均值的差的绝对值尽量要小(上面两个案例都符合这个原则~换句话说划分原则就是趋向于数据的平均值)~这个如果证明成立就可以大大降低时间复杂度~算法就变得非常简单了~

不断地求相邻两数字和， 每次保留最小的和那个结果

一直循环 N - K 次

/**

 *\file test.cc

 */
#include <stdio.h>
#include <assert.h>

#define    MAX_ARY_SIZE    (100)    ///<

unsigned int id_ary[MAX_ARY_SIZE];
unsigned int val_ary[MAX_ARY_SIZE];

struct{
    
    unsigned int idx;    ///< 真实下标
    unsigned int val;
}swap[MAX_ARY_SIZE];

int main(void)
{
    unsigned int n = 0, sn = 0;
    unsigned int k = 0;
    unsigned int i = 0;
    
    scanf("%u %u", &n, &k);
    assert(n >= k);
    sn = n;
    
    /* 循环输入 */
    for (i = 0; i < n; ++i){
        
        scanf("%u", &val_ary[i]);
        swap[i].val = val_ary[i];
        swap[i].idx = i; 
        /* 初始化id */
        id_ary[i] = i;
    }
    
    while (k < sn){
        
        unsigned int sum = 0, tmp = 0;
        unsigned int min_idx = 0;
        
        sum = swap[0].val + swap[1].val;
        for (i = 1; i < sn - 1; ++i){
            
            tmp = swap[i].val + swap[i + 1].val;
            if (sum > tmp){
                
                min_idx = i;
                sum = tmp;
            }
        }
        
        id_ary[swap[min_idx].idx] = id_ary[swap[min_idx + 1].idx];
        swap[min_idx].val += swap[min_idx + 1].val;
        /* 调整位置 */
        for (i = min_idx + 1; i < sn - 1; ++i){
        
            swap[i].val = swap[i+1].val;
            swap[i].idx = swap[i+1].idx;
        }
        
        sn--;
    }
    
    /* 输出结果 */
    for (i = 0; i < n; ++i){
        
        if ((0 < i) && (i < n) && (id_ary[i-1] != id_ary[i])){
        
            printf("|");
        }
        printf(" %u ", val_ary[i]);
    }
    printf("\n");
    
    return 0;
}

#if 0

 ~/test # ./tests 
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 
#endif

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

方法不对。。。
~/test # ./tests
4 2
6 2 2 6
 6  2  2 | 6

请问怎么记录当前划分数据的权值和保存状态
设sum[n,k]
sum[i,j]= min{sum[i,j],Math.pow(a[i][j])}
感觉不太对

感觉自己说得复杂了~当然有些时候复杂点的效率会高一点~不过前提是要正确才行~
所以理解不了还是先从最简单的开始想起~其实我自己也不知道自己的是否正确~

试试求划分数据的平均值~然后让每一组划分数据尽量趋向于平均值~看看是否正确？~
如果该方法不正确的话……就要另外想算法了~实在不行全就组合遍历垫底~

写了个极端测试~
N=5 K=3
100 |1 1| 1 1

明显是这样~

第一次数据的平均值是104/3;
第二次数据的平均值是4/2;

所以感觉是每划分一次就要从新求一次平均值以确保数据平衡~


1 1 |1 1|100

逆序划分结果不变才是正确的~
所以感觉还是要每个数据都要充分利用~
看来还得要老老实实去每个状态判断才行~

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

感觉就算没有满足要求思路也有一定参考价值~在原来的基础上多考虑点东西应该可以行得通~还是发一下没有满足条件的代码~可以看看大体思路~感觉改好不是不可以~要整体变动划分标记的值~比较麻烦~如果重做的话可以考虑用结构体进行简化一下~

上楼依然是水贴~

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>//划分整数问题~程序有误~

void Init(int** s,int** p,int* N,int* K);     //初始化数据
void Print(int s[],int N);                    //输出数据
void Print_Result(int s[],int p[],int N);     //输出执行结果
int Count(int s[],int i,int j);               //求和

void fun(int s[],int p[],int N,int K);       //函数执行主体

int main()
{
    int N=0;
    int K=0;

    int* s=NULL;
    int* p=NULL;

    Init(&s,&p,&N,&K);

    puts("测试输入数据如下:");
    Print(s,N);                //开始检查初始化数据

    fun(s,p,N,K);

    puts("划分结果如下:");
    Print_Result(s,p,N);

    return 0;
}

void Init(int** s,int** p,int* N,int* K)   //初始化数据
{
    int i=0;

    puts("请输入N K的值(中间用空格隔开):");
    scanf("%d%d",N,K);

    *s=(int*)malloc(*N*sizeof(int));
    *p=(int*)malloc(*K+1*sizeof(int));

    if (*s==NULL||*p==NULL)
    {
        puts("分配空间失败!");
        exit(0);
    }

    if (*N<=0||*K<=0||*N<*K)
    {
        puts("输入数据出错!");
        exit(0);
    }

    printf("请输入%d个数:\n",*N);
    for (i=0;i<*N;++i)
        scanf("%d",&((*s)[i]));

    for (i=0;i<*K;++i)
        (*p)[i]=i;

    (*p)[i]=*N;
}

void Print(int s[],int N)
{
    int i=0;

    for (i=0;i<N;++i)
        printf("%-4d",s[i]);

    puts("");
}

int Count(int s[],int i,int j)      //求两个划分区间的和
{
    int sum=0;

    while (i<j)
        sum+=s[i++];

    return sum;
}

void fun(int s[],int p[],int N,int K)       //函数执行主体
{
    int i=0;              //循环变量
    int point=K-1;        //指针数据指向尾部

    while (1)
    {
        point=K-1;

        while (point>0&&(Count(s,p[point-1],p[point])>=Count(s,p[point],p[point+1])||p[point+1]-p[point]==1))
            --point;   //这里判断条件少考虑了跨划分标记遍历的情况,要完善一下,感觉要新增一个判断函数还要改变遍历标记的值

        if (point==0)
            break;

        while (p[point+1]-p[point]>1&&Count(s,p[point-1],p[point])<Count(s,p[point],p[point+1]))
            ++p[point];
    }
}

void Print_Result(int s[],int p[],int N)
{
    int i=0;
    int j=1;

    for (i=0;i<N;++i)
    {
        if (i==p[j])
        {
            printf("|  ");
            j++;
        }

        printf("%-4d",s[i]);
    }

    puts("");
        
}

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

感谢大神耐心的回复！

我想分两段计算 就前面和后面比大小 可是不知道该怎么储存计算值和用哪一部分相比较
如果用三段for循环
minSun(s[n],group[k],n)
s[n]=s1...sn  //初始化输入
group[1]=s1[1] s2[1] ... s[i-1][1]  //n 分组
group[k] =s[i][k] s[i+1][k]...s[n][k]
min=-oo
for i=1 to n
for j=1to k
for t<i-1
    ss[i]=(s[t]+...+s[i])  //第一段和从s[t]加到s[i]
    q=min(q, ss[i]+minSum(ss,group[n-i][j],n-i))   //剩下的长为n-i，最大和sum[n-i] 在N里面从I 到L 位置最小和   
                                                                                          //这里有点懵不知道怎么写
for i=to k
    temp=group[1]^2+...+group[k]^2         // 可是这样感觉就全部遍历一遍了不太好
    best = min(temp,best)
 return best

n9  k4
1 2 3 4 5 6 7 8 9
1 2 3 4 | 5 6 | 7 | 8| 9 |
n5 k3
5 7 11 4 21
5 7 | 11 4 |21

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