最大m子段和問題：給定由n個(gè)整數(shù)（可能為負(fù)）組成的序列a1、a2、a3...,an,以及一個(gè)正整數(shù)m，要求確定序列的m個(gè)不想交子段，使這m個(gè)子段的總和最大！
設(shè)b(i,j)表示數(shù)組a的前j項(xiàng)中i個(gè)子段和的最大值，
并且第i個(gè)子段包含a[j](1<=i<=m,i<=j<=n)，則所求的最優(yōu)值為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個(gè)包含a[j-1]和a[j]，maxb(i-1,t)+a[j]表示第i個(gè)子段僅包含a[j]。
這中定義很強(qiáng)悍，尤其是黃色標(biāo)記部分，直接把b(i,j)把a(bǔ)[j]限制在第i段內(nèi)，然后再分a[j-1]和a[j]都在子段內(nèi)和只有a[j]，特殊的當(dāng)m=1時(shí)，b(1,j)=max(b(1,j-1)+a[j],a[j]),1<=j<=n;如果翻譯成文字的話，就是說在數(shù)組j位置的最大和子段（包含a[j]）等于數(shù)組在j-1位置的最大和子段（包含a(j-1)）加上a[j]和最大和子段只有a[j]的情況的最優(yōu)值，當(dāng)然所求解可以表示為maxb(1,j)(1<=j<=n)；
其實(shí)如果光從b(1,j)=max(b(1,j-1)+a[j],a[j])這個(gè)等式本生出發(fā)我們很容易的觀察出b(1,j-1)的正負(fù)直接決定著b(1,j)的取值，然后我們可以產(chǎn)生這中想法，如果b(1,j-1)為正，我就繼續(xù)加，如果為負(fù)我就重新開始加！！！這樣的話，寫成程序就更簡單，其實(shí)就是前面我寫的最大子段和的動態(tài)規(guī)劃方法的解釋。。。（今天終于明白了！！！）
代碼如下：
#include<stdio.h>
int MaxSum1(int m,int n,int *a)//m為切割段數(shù)，n為數(shù)組大小
{
int i,j,k,sum;
if(n<m||m<1)
return 0;
int **b =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;
}
//教科書上又進(jìn)行了代碼優(yōu)化，如下
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;
} 對于這段代碼我按著思想看了一遍，沒有仔細(xì)推敲過，不知道會不會是個(gè)禍患，但是測試通過了！！！
posted on 2010-09-11 09:48
jince 閱讀(732)
評論(0) 編輯 收藏 引用 所屬分類:
算法設(shè)計(jì)與分析