3.7-2动态规划--图像压缩举例子和写代码

问题描述（再写一遍）

这篇文章是接着上面这一篇写的，就是写一个例子方便理解，模拟填写数组的过程

l: l[i]存放第i段长度, 表中各项均为8位长，限制了相同位数的元素<=256

B: b[i]存放第i段中像素的存储位数,表中各项均为3位长。最长的像素是八位表示一个像素，用二进制来表示：000/001/010/011/100/101/110/111。存储位数最多为3位

P: {p1,…p n2}以变长格式存储的像素的二进制串。分成m段，S1，S2，...，Sm

最优数组含义：s[i]，1≤i≤n，是像素序列{p1,…,pi}（注意，是pi）的最优分段所需的存储位数。

一开始我们也不知道分了几段，m是最后backtrack回溯的时候才能确定下来。

像素序列4，6，5，7，129，138，1的最优分段,下标从1开始

后面的继承前面的分段组合方式，然后一直往后加

遵循这样的递推关系

 伪代码：

构造最优解： 最优分段的最后一段的段长度和像素位数分别存储于l[n], b[n]中,前一段的段长度和像素位数存储于**l[n - l[n]]和 b[n - l[n]]**中.
以此类推,由算法计算出的l和b可在O(n)时间内构造出相应的最优解.

代码

1.  
   // 图像压缩
2.  
   #include<bits/stdc .h>
3.  
   using namespace std;
4.  
   int length(int i) //计算像素点p所需要的存储位数
5.  
   {
6.  
   int k = 1;
7.  
   i = i/2;
8.  
   while(i>0)
9.  
   {
10.  
    k ;
11.  
    i = i/2;
12.  
    }
13.  
    return k;
14.  
    }
15.  
    void Compress(int n, int p[], int s[], int l[], int b[]) //令s[i]为前i个段最优合并的存储位数
16.  
    {
17.  
    int Lmax = 256, header = 11;
18.  
    s[0] = 0;
19.  
    for(int i=1; i<=n; i ) //i表示前几段
20.  
    {
21.  
    b[i] = length(p[i]); //计算像素点p需要的存储位数
22.  
    int bmax = b[i];
23.  
    cout<<i<<"bmax: "<<bmax<<endl;
24.  
    s[i] = s[i-1] bmax; //故下面j从2开始
25.  
    l[i] = 1;
26.  
    for(int j=2; j<=i && j<=Lmax; j ) //递推关系:s[i]= min(1<=j<=i)(lsum(i-j 1, i)<=256) {s[i-j] lsum(i-j 1,i)*bmax(i-j 1,i) } 11
27.  
    {
28.  
    if(bmax < b[i-j 1])
29.  
    bmax = b[i-j 1];
30.  
    if(s[i] > s[i-j] j*bmax) //因为一开始所有序列并没有分段,所以可以看作每一段就是一个数,故lsum(i-j 1, i) = j;
31.  
    {
32.  
    s[i] = s[i-j] j*bmax;
33.  
    l[i] = j; //最优断开位置,l[i]表示前i段的最优分段方案中应该是在i-j处断开 比如l[5] = 3,这表示前五段的最优分段应该是(5-3=2)处断开,s[5] = s[2] 3*bmax
34.  
    //即 12 | 345,以此类推,得到l[n];之后构造最优解时再由l[n]向前回溯
35.  
    }
36.  
    }
37.  
    s[i] = header;
38.  
    }
39.  
    }
40.  
    void Traceback(int n, int &m, int s[], int l[])
41.  
    {
42.  
    if(n == 0) return;
43.  
    Traceback(n-l[n], m, s, l);
44.  
    s[m ] = n-l[n]; //重新为s[]数组赋值，用来存储分段位置
45.  
    }
46.  
    void Output(int s[], int l[], int b[], int n)
47.  
    {
48.  
    cout<<"The optimal value is "<<s[n]<<endl;
49.  
    int m = 0;
50.  
    Traceback(n, m, s, l);
51.  
    s[m] = n;
52.  
    cout<<"Decompose into "<<m<<" segments "<<endl;
53.  
    for(int j=1; j<=m; j )
54.  
    {
55.  
    l[j] = l[s[j]];
56.  
    b[j] = b[s[j]];
57.  
    }
58.  
    for(int j=1; j<=m; j )
59.  
    cout<<"段长度:"<<l[j]<<" 所需存储位数:"<<b[j]<<endl;
60.  
    }
61.  
    int main()
62.  
    {
63.  
    int n;
64.  
    while(cin>>n && n)
65.  
    {
66.  
    int p[n 1];
67.  
    int s[n 1], l[n 1], b[n 1];
68.  
    for(int i=1; i<=n; i )
69.  
    cin>>p[i];
70.  
    Compress(n, p, s, l, b);
71.  
    int m=0;
72.  
    Traceback(n, m, s, l);
73.  
    Output(s, l, b, n);
74.  
    memset(p, sizeof(p), 0);
75.  
    }
76.  
    system("pause");
77.  
    return 0;
78.  
    }
79.  
    /*6
80.  
    10 12 15 255 1 2*/

这篇好文章是转载于：学新通技术网