<算法设计与分析> --王晓东

　　

题目描述和解析参照：  他在那里分析得非常的详细。我也是按照这种思路来解的，而且算法设计与实现的课件上也是这么个解法。

主要是理解这个公式，还有就是定义的几个数组s[],l[],b[]的含义。那么就可以自下而上的解决问题了。动态规划的题目做多了，一看到这种题目我们就应该能找到具体的方法，那就是每次不断的变换K的位置，然后查找最优解。

我的代码实现：

#include 
     
      #include 
      
       #include 
       
        #define MAX 20int max_bit(int p[],int start,int end);void compress(int s[],int p[],int b[],int l[],int n);void back_tack(int s[],int b[],int l[],int n);int seg;int main(){    int i,l[MAX],b[MAX],s[MAX];    int p[] = {
   10,12,15,255,1,2};    for (i = 0; i < MAX; i++)        s[i] = 999;    compress(s,p,b,l,6);    printf("最小空间为：%d\n",s[6]);    seg = 0;    back_tack(s,b,l,6);    printf("总共分为%d段\n",seg);    return 0;}int max_bit(int p[],int start,int end){    int i,bit_max,max_value;        max_value = 0;    for (i = start; i < end; i++)        //求出最大值        max_value = max_value > p[i] ? max_value : p[i];    bit_max = 1;            //最大值至少要多少的存储位    i = max_value / 2;    while(i > 0)    {        bit_max++;        i = i / 2;    }    return bit_max;}void compress(int s[],int p[],int b[],int l[],int n){    int i,k,tmp;    int bit_max;        s[0] = 0;    s[1] = max_bit(p,0,1) + 11;    l[1] = 0;    for (i = 2; i <= n; i++){                //控制s[i]         for (k = 0; k < i; k++){            //            bit_max = max_bit(p,k,i);            tmp = s[k] + (i-k)*bit_max + 11;            //s[i] = s[i] < tmp ? s[i] : tmp;            if (s[i] > tmp){                s[i] = tmp;                l[i] = i-k;                b[i] = bit_max;            }        }    }}void back_tack(int s[],int b[],int l[],int n){    if (n == 0){        return;    } else {        seg += 1;        back_tack(s,b,l,n-l[n]);        printf("段长度：%d，所需存储位数：%d\n",            l[n],b[n]);    }}//        2013/9/23  19:34