voip
风的方向
厚德致远,博学敦行!
posts - 52,comments - 21,trackbacks - 0
         最大m子段和问题:给定由n个整数(可能为负)组成的序列a1、a2、a3...,an,以及一个正整数m,要求确定序列的m个不想交子段,使这m个子段的总和最大!
         设b(i,j)表示数组a的前j项中i个子段和的最大值,并且第i个子段包含a[j](1<=i<=m,i<=j<=n),则所求的最优值为maxb(m,j)(m<=j<=n)。在这种定义下b(i,j)的递推公式:b(i,j)=max{b(i,j-1)+a[j],maxb(i-1,t)+a[j](i-1<=t<j)}(1<=i<=m,i<=j<=n);b(i,j-1)+a[j]表示第i个包含a[j-1]和a[j],maxb(i-1,t)+a[j]表示第i个子段仅包含a[j]。
         这中定义很强悍,尤其是黄色标记部分,直接把b(i,j)把a[j]限制在第i段内,然后再分a[j-1]和a[j]都在子段内和只有a[j],特殊的当m=1时,b(1,j)=max(b(1,j-1)+a[j],a[j]),1<=j<=n;如果翻译成文字的话,就是说在数组j位置的最大和子段(包含a[j])等于数组在j-1位置的最大和子段(包含a(j-1))加上a[j]和最大和子段只有a[j]的情况的最优值,当然所求解可以表示为maxb(1,j)(1<=j<=n);其实如果光从b(1,j)=max(b(1,j-1)+a[j],a[j])这个等式本生出发我们很容易的观察出b(1,j-1)的正负直接决定着b(1,j)的取值,然后我们可以产生这中想法,如果b(1,j-1)为正,我就继续加,如果为负我就重新开始加!!!这样的话,写成程序就更简单,其实就是前面我写的最大子段和的动态规划方法的解释。。。(今天终于明白了!!!)

代码如下:

#include<stdio.h>

int MaxSum1(int m,int n,int *a)//m为切割段数,n为数组大小
{
    
int i,j,k,sum;
    
if(n<m||m<1)
        
return 0;
    
int **=new int *[m+1];

    
for(i=0;i<=m;i++)
        b[i]
=new int[n+1];
    
for(i=0;i<=m;i++)
        b[i][
0]=0;
    
for(j=1;j<=n;j++)
        b[
0][j]=0;

    
for(i=1;i<=m;i++)
        
for(j=i;j<=n-m+i;j++)
        
{
            
if(j>i)
            
{
                b[i][j]
=b[i][j-1]+a[j];
                
for(k=i-1;k<j;k++)
                
{
                    
if(b[i][j]<b[i-1][k]+a[j])
                        b[i][j]
=b[i-1][k]+a[j];
                }

            }

            
else
            
{
                b[i][j]
=b[i-1][j-1]+a[j];
            }

        }

    sum
=0;
    
for(j=m;j<=n;j++)
        
if(sum<b[m][j])
            sum
=b[m][j];
    delete b;
    
return sum;
}


//教科书上又进行了代码优化,如下
int MaxSum(int m,int n,int *a)
{
    
int i,max,j,sum;
    
if(n<m||m<1)
        
return 0;

    
int *b=new int[n+1];
    
int *c=new int[n+1];
    b[
0]=0;
    c[
0]=0;
    
for(i=1;i<=m;i++)
    
{
        b[i]
=b[i-1]+a[i];
        c[i
-1]=b[i];
        max
=b[i];
        
for(j=i+1;j<=i+n-m;j++)
        
{
            b[j]
=b[j-1]>c[j-1]?b[j-1]+a[j]:c[j-1]+a[j];
            c[j
-1]=max;
            
if(max<b[j])
                max
=b[j];
        }

        c[i
+n-m]=max;
    }


    sum
=0;
    
for(j=m;j<=n;j++)
        
if(sum<b[j]) 
            sum
=b[j];
    
return sum;
}



int main()
{
    
int n,m;
    
int a[100],i;
    
while(scanf("%d %d",&m,&n)!=EOF)
    
{
        
for(i=1;i<=n;i++)
            scanf(
"%d",&a[i]);
        printf(
"%d\n",MaxSum(m,n,a));
    }

    
return 0;
}

      对于这段代码我按着思想看了一遍,没有仔细推敲过,不知道会不会是个祸患,但是测试通过了!!!
posted on 2010-09-11 09:48 jince 阅读(609) 评论(0)  编辑 收藏 引用 所属分类: 算法设计与分析

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


哈哈哈哈哈哈