最小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 阅读(3534) 评论(0)  编辑 收藏 引用