<算法設計與分析> --王曉東

　　

題目描述和解析參照：http://blog.csdn.net/liufeng_king/article/details/8648195? 他在那里分析得非常的詳細。我也是按照這種思路來解的，而且算法設計與實現的課件上也是這么個解法。

主要是理解這個公式，還有就是定義的幾個數組s[],l[],b[]的含義。那么就可以自下而上的解決問題了。動態規劃的題目做多了，一看到這種題目我們就應該能找到具體的方法，那就是每次不斷的變換K的位置，然后查找最優解。

我的代碼實現：

#include <stdio.h> #include <stdlib.h> #include <math.h>#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

?

?

轉載于:https://www.cnblogs.com/Jason-Damon/p/3335566.html

總結

以上是生活随笔為你收集整理的动态规划--图像压缩的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。