最小m段和问题

                    最小m段和问题

给定 n 个整数组成的序列,现在要求将序列分割为 m 段,每段子序列中
的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达
到最小?

动态规划的解法:

1.    阶段数为m.

2.    状态转移方程:

     f[i][j]=min max{ f[i][1]-f[k][1],f[k][j-1]}

  其中1<=k<i;j<= i <=n; 1<= j <= m;

  初态:f[i][1]=f[i-1][1]+a[i]

  最优值为f[n][m]。

3.    对于第j阶段中的每个 i, (j<=i <=n),考虑将1到i的序列分为j段子序列,且第j段序列从k开始到i,
由最优子结构性质,只需比较第j段序列和第j-1阶段的最优值即可。

  

  决策变量:第j段序列分配i-k个元素

 

源代码:

 

 

 1#include <iostream>
 2#include <fstream>
 3using namespace std;
 4
 5int main(){
 6    int n,m;
 7    ifstream fin("sum1.in");
 8    if(!fin){
 9        cout<<"can not open the file !"<<endl;
10        system("pause");
11        return 0;
12    }

13    
14    fin>>n>>m;
15    int i=n;
16    int a[n+1];
17    for(i=1;i<=n;i++){
18        fin>>a[i];
19    }

20    fin.close();
21    int f[n+1][m+1];
22    //初始化第一阶段信息 
23    f[0][1]=0;
24    for(int i=1;i<=n;i++){
25        f[i][1]=f[i-1][1]+a[i];
26    }

27    int tmp,maxN=0;
28    for(int j=2;j<=m;j++){
29        for(int i=j;i<=n;i++){
30            tmp=1000000;
31            for(int k=1;k<i;k++){
32                maxN=std::max(f[i][1]-f[k][1],f[k][j-1]) ;
33                if(tmp>maxN)tmp=maxN;
34            }

35           f[i][j]=tmp;
36        }

37    }

38    cout<<f[n][m]<<endl;
39    system("pause");
40     return 0;
41    }

42         
43        
44

   
  
测试:
9 3
9 8 7 6 5 4 3 2 1

输出
17

2010年5月31日11:08:38 

 

posted on 2010-05-31 11:10 bluedream 阅读(3404) 评论(0)  编辑 收藏 引用


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


<2010年5月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿

随笔档案(6)

搜索

最新评论

阅读排行榜

评论排行榜