贪心算法哈夫曼编码
㈠ 几种经典算法回顾
今天无意中从箱子里发现了大学时学算法的教材《算法设计与分析》，虽然工作这么几年没在什么地方用过算法，但算法的思想还是影响深刻的，可以在系统设计时提供一些思路。大致翻了翻，重温了一下几种几种经典的算法，做一下小结。分治法动态规划贪心算法回溯法分支限界法分治法1）基本思想将一个问题分解为多个规模较小的子问题，这些子问题互相独立并与原问题解决方法相同。递归解这些子问题，然后将这各子问题的解合并得到原问题的解。2）适用问题的特征该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题3）关键如何将问题分解为规模较小并且解决方法相同的问题分解的粒度4）步骤分解->递归求解->合并 divide-and-conquer(P) { if ( | P | <= n0) adhoc(P); //解决小规模的问题 divide P into smaller subinstances P1,P2,...,Pk；//分解问题 for (i=1,i<=k,i++) yi=divide-and-conquer(Pi); //递归的解各子问题 return merge(y1,...,yk); //将各子问题的解合并为原问题的解 }google的核心算法MapRece其实就是分治法的衍生5）分治法例子：合并排序规约过程：动态规划1）基本思想将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的，如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算2）适用问题的特征最优子结构在递归计算中，许多子问题被重复计算多次3）步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。贪心算法1）基本思想贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择2）适用问题的特征贪心选择性质，即所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。最优子结构性质3）步骤：不断寻找局部最优解4）例子：找硬币，哈夫曼编码，单源最短路径，最小生成树（Prim和Kruskal） 最小生成树图示：回溯法1）基本思想在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索2）适用问题的特征：容易构建所解问题的解空间3）步骤定义问题的解空间 确定易于搜索的解空间结构以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索 4）回溯法例子：N皇后问题分支限界法1）基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2）分支限界法例子：单源最短路径问题问题描述：在下图所给的有向图G中，每一边都有一个非负边权。
㈡ 霍夫曼编程采用的是哪种编程原理
霍夫曼编码的matlab实现一、实验内容：用Matlab语言编程实现霍夫曼（Huffman）编码。二、实验原理及编码步骤：霍夫曼（Huffman）编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号，而将较短的编码码字分配给较大概率的信源输出。算法是：在信源符号集合中，首先将两个最小概率的信源输出合并为新的输出，其概率是两个相应输出符号概率之和。这一过程重复下去，直到只剩下一个合并输出为止，这个最后的合并输出符号的概率为1。这样就得到了一张树图，从树根开始，将编码符号1和0分配在同一节点的任意两分支上，这一分配过程重复直到树叶。从树根到树叶途经支路上的编码最后就构成了一组异前置码，就是霍夫曼编码输出。
㈢ 霍夫曼编码 用c语言实现
以前写的，证明最优子结构，随便一本算法书上就有.
#include<stdio.h>
#include<stdlib.h>
#define
NIL
-2
#define
Size_Max_bm
30
#define
left(i)
(2*(i)+1)
#define
right(i)
(2*(i)+2)
#define
swap(a,b)
{cjys
t;t=(a);(a)=(b);(b)=t;}
#define
parent(i)
((i)%2?((i)-1)/2:((i)-2)/2)typedef
struct
cjys
{
char
sj;
int
pl;
struct
cjys
*left;
struct
cjys
*right;
}cjys;typedef
struct
cjdl
{
int
size;
int
leapsize;
cjys
*p;
}cjdl;
cjys
*fpnn(void);
void
input(cjdl
*p);
cjys
*fpnn(void);
void
zxdwh(cjys
*p,
int
i,
int
leapsize);
void
rd(cjdl
*p,
cjys
tp);
cjys
cd(cjdl
*p);
void
hbs(cjdl
*p);
cjys
*cjs(cjdl
*p);
void
bls(cjys
*p,int
*jl,
int
i);
void
disp(char
*tp,
cjys
*p);int
main()
{
cjdl
p;
char
x[255];
cjys
*re=NULL;
int
jl[Size_Max_bm];
input(&p);
re=cjs(&p);
printf("对照编码图为:\n");
bls(re,jl,0);
freopen("CON","r",stdin);
printf("输入Huffman码(VLC):");
scanf("%s",x);
disp(x,re);
system("pause");
}
void
input(cjdl
*p)
{
int
i;
cjys
*tp;
tp=fpnn();
printf("输入字母个数:");
scanf("%d",
&p->size);
p->p=malloc(sizeof(cjys)*p->size);
p->leapsize=0;
for(i
=
0;
i
<
p->size;i++)
{
printf("输入第%d字母:",i+1),scanf("
%c",&tp->sj);
printf("输入出现次数(频率整数):"),scanf("%d",&tp->pl);
rd(p,*tp);
}
free(tp);
}
cjys
*fpnn(void)
{
cjys
*p=NULL;
p=malloc(sizeof(cjys));
p->left=NULL;
p->right=NULL;
return
p;
}
void
zxdwh(cjys
*p,
int
i,
int
leapsize)
{
int
l=left(i),
r=right(i),
mini=i;
if(l<leapsize
&&
p[l].pl<p[mini].pl)
mini=l;
if(r<leapsize
&&
p[r].pl<p[mini].pl)
mini=r;
if(mini
!=
i)
{
swap(p[i],p[mini]);
zxdwh(p,mini,leapsize);
}
}
void
rd(cjdl
*p,
cjys
tp)
{
if(p->leapsize
==
p->size)
{
printf("队列已满!");
exit(0);
}
p->p[p->leapsize]=tp;
int
j=p->leapsize,k=parent(j);
while(k>=0
&&
p->p[j].pl
<
p->p[k].pl)
{
swap(p->p[j],p->p[k]);
j=k;
k=parent(j);
}
p->leapsize++;
}
cjys
cd(cjdl
*p)
{
if(p->leapsize
==
0)
{
printf("队列已空!");
exit(0);
}
cjys
tp=p->p[0];
p->leapsize--;
p->p[0]=p->p[p->leapsize];
zxdwh(p->p,0,p->leapsize);
return
tp;
}
void
hbs(cjdl
*p)
{
cjys
*p1=NULL,
*p2=NULL;
cjys
tp;
p1=fpnn();
p2=fpnn();
*p1=cd(p);
*p2=cd(p);
tp.left=p1;
tp.right=p2;
tp.pl=p1->pl+p2->pl;
tp.sj=NIL;
rd(p,tp);
}cjys
*cjs(cjdl
*p)
{
int
i,
n=p->leapsize;
cjys
*tp=NULL;
tp=fpnn();
for(i
=
0;
i
<
n-1;
i++)
hbs(p);
*tp=p->p[0];
return
tp;
}
void
bls(cjys
*p,
int
*jl,
int
i)
{
if(p
==
NULL)
return;
if(p->sj!=NIL)
{
int
i2;
printf("%c:",p->sj);
for(i2
=
0;
i2
<
i;
i2++)
printf("%d",jl[i2]);
printf("\n");
}
jl[i]=0;
bls(p->left,jl,i+1);
jl[i]=1;
bls(p->right,jl,i+1);
}
void
disp(char
*tp,
cjys
*p)
{
cjys
*ttp=NULL;
int
pd=0;
while(1)
{
ttp=p;
while(1)
{
if(ttp->sj
!=
NIL)
{
printf("%c",ttp->sj);
break;
}
if(*tp
==
'\0')
{
pd=1;
break;
}
if(*tp++
==
'0'
)
ttp=ttp->left;
else
ttp=ttp->right;
}
if(pd)
break;
}
}
㈣ 贪心算法：最小生成树，霍夫曼编码
连通图： 在无向图中，若任意两个顶点vi与vj都有路径相通，则称该无向图为连通图。
强连通图（Strongly Connected Graph） 是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。
连通网： 在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
生成树： 一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
最小生成树： 在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
示例：
分别使用 Kruskal算法 和 Prim算法 ，找出下图的最小生成树。
使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
具体步骤
1.将信源符号的概率按减小的顺序排队。
2.把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在右边，直到最后变成概率1。
3.画出由概率1处到每个信源符号的路径，顺序记下沿路径的0和1，所得就是该符号的霍夫曼码字。
4.将每对组合的左边一个指定为0，右边一个指定为1（或相反）。
示例：
假设字符a,b,c,d,e出现的概率分别为1/2,1/4,1/8,1/16,1/16。
1.求出各字符哈夫曼编码表。
2.假设一个文件有1,000,000个字符，求出编码之后文件的字节长度。
A:0
B:10
C:110
D:1110
E:1111
a所占长度l1为：（1,000,000/2） 1
b所占长度l2为：（1,000,000/4） 2
c所占长度l3为：（1,000,000/8） 3
d所占长度l4为：（1,000,000/16） 4
e所占长度l5为：（1,000,000/16）*4
文件的总长度l = l1 + l2 + l3 + l4 + l5 = 1875000
㈤ 算法09-贪心算法
贪心算法与动态规划的不同在于它对每个子问题的解决方案都作出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
很多情况下，可以在某一步用贪心算法，全局再加一个搜索或递归或动态规划之类
贪心法可以解决一些最优化问题，如:求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题，贪心法一般不能得到我们所要求的答案。
一单一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
当硬币可选集合固定:Coins = [20,10,5,1],求最少几个硬币可以拼出总数。比如total=36。
36 - 20 = 16 20
16 - 10 = 6 20 10
6 - 5 = 1 20 10 5
1 - 1 = 0 20 10 5 1
前面这些硬币依次是后面硬币的整数倍，可以用贪心法，能得到最优解，
贪心法的反例
非整除关系的硬币，可选集合:Coins = [10,9,1],求拼出总数为18最少需要几个硬币？
最优化算法:9 + 9 = 18 两个9
贪心算法:18 - 10 = 8 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 = 0 八个1
简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解成为最优子结构。
贪心算法与动态规划的不同在于它对每个子问题的最终方案都作出选择，不能回退。
动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
提示：
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。
想要达到这样的效果，只要让移动下标，最大只能移动到nums.size - 2的地方就可以了。
因为当移动下标指向nums.size - 2时：
如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置），如图：
如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。如图：
机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：
-2 ：向左转 90 度
-1 ：向右转 90 度
1 <= x <= 9 ：向前移动 x 个单位长度
在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点 obstacles[i] = (xi, yi) 。
机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续尝试进行该路线的其余部分。
返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。（即，如果距离为 5 ，则返回 25 ）
注意：
北表示 +Y 方向。
东表示 +X 方向。
南表示 -Y 方向。
西表示 -X 方向。
示例 1：
输入：commands = [4,-1,3], obstacles = []
输出：25
解释：
机器人开始位于 (0, 0)：
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：[5,5,10]
输出：true
示例 3：
输入：[10,10]
输出：false
示例 4：
输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
示例 4：
输入：coins = [1], amount = 1
输出：1
示例 5：
输入：coins = [1], amount = 2
输出：2
㈥ 哈夫曼编码码长怎么算
设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。
霍夫曼编码是变长编码，思路：对概率大的编的码字短，概率小的编的码字长，这样一来所编的总码长就小，这样编码效率就高。上面那样求是不对的，除非你这6个码字是等概率的，各占1/6。应该用对应的概率*其对应得码长，再求和。
实际应用中
除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。
按照CCITT标准，需要统计2×1728种游程（长度），这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。
㈦ 贪心算法实现哈夫曼编码
// 哈夫曼编码(算法)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码
typedef struct
{
unsigned int weight; //用来存放各个结点的权值
unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针
} HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树
//选择两个parent为0，且weight最小的结点s1和s2
void Select(HuffmanTree *ht,int n,int *s1,int *s2)
{
int i,min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0)
{
min=i;
break;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0)
{
if((*ht)[i].weight<(*ht)[min].weight)
min=i;
}
}
*s1=min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0 && i!=(*s1))
{
min=i;
break;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0 && i!=(*s1))
{
if((*ht)[i].weight<(*ht)[min].weight) min=i;
}
}
*s2=min;
}
//构造哈夫曼树ht。w存放已知的n个权值
void CrtHuffmanTree(HuffmanTree *ht,int *w,int n)
{
int m,i,s1,s2;
m=2*n-1;
*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1; i<=n; i++) //1--n号存放叶子结点，初始化
{
(*ht)[i].weight=w[i];
(*ht)[i].LChild=0;
(*ht)[i].parent=0;
(*ht)[i].RChild=0;
}
for(i=n+1; i<=m; i++)
{
(*ht)[i].weight=0;
(*ht)[i].LChild=0;
(*ht)[i].parent=0;
(*ht)[i].RChild=0;
} //非叶子结点初始化
printf("\nHuffmanTree: \n");
for(i=n+1; i<=m; i++) //创建非叶子结点，建哈夫曼树
{ //在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0
//且weight最小的结点，其序号分别赋值给s1、s2
Select(ht,i-1,&s1,&s2);
(*ht)[s1].parent=i;
(*ht)[s2].parent=i;
(*ht)[i].LChild=s1;
(*ht)[i].RChild=s2;
(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;
printf("%d (%d, %d)\n",(*ht)[i].weight,(*ht)[s1].weight,(*ht)[s2].weight);
}
printf("\n");
} //哈夫曼树建立完毕
//从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码
void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)
{
char *cd;
int i,start,p;
unsigned int c;
hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配n个编码的头指针
cd=(char *)malloc(n*sizeof(char)); //分配求当前编码的工作空间
cd[n-1]='\0'; //从右向左逐位存放编码，首先存放编码结束符
for(i=1; i<=n; i++) //求n个叶子结点对应的哈夫曼编码
{
start=n-1; //初始化编码起始指针
for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //从叶子到根结点求编码
if( (*ht)[p].LChild==c) cd[--start]='0'; //左分支标0
else cd[--start]='1'; //右分支标1
hc[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间
strcpy(hc[i],&cd[start]);
}
free(cd);
for(i=1; i<=n; i++)
printf("HuffmanCode of %3d is %s\n",(*ht)[i].weight,hc[i]);
printf("\n");
}
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,i,n,wei,m;
printf("\nn = " );
scanf("%d",&n);
w=(int *)malloc((n+1)*sizeof(int));
printf("\ninput the %d element's weight:\n",n);
for(i=1; i<=n; i++)
{
printf("%d: ",i);
fflush(stdin);
scanf("%d",&wei);
w[i]=wei;
}
CrtHuffmanTree(&HT,w,n);
CrtHuffmanCode(&HT,&HC,n);
}
㈧ 用动态规划解决钢条切割问题时它的最优子结构是什么
1、两种重要算法思想： 动态规划，贪心算法
2、动态规划：
基本原理：动态规划英文名dynamic programming。其中pogramming指的是表格法，而非编写计算机程序。因此，可以初步得出动态规划的基本思想：将一个具有最优子结构性质的问题分成若干个子问题，在求解过程中，记录下子问题的结果，存储在一个表格中，使得公共的子问题只需要计算一次。书中给出的基本原理：动态规划将问题分成若干个相互重叠的子问题，递归的求解子问题，保存子问题的解，再将它们的解组合起来，求出原问题的解。
从基本原理中可以看出动态规划需要满足两个条件，最优子结构和子问题重叠。
最优子结构：书中定义：问题的最优解由相关子问题的最优解组合而成，一个问题的最优解包含其子问题的最优解。典型的有背包问题和钢条切割我问题。所谓子问题就是一中组合，将一个问题分成许多子问题的集合。某个子问题转化为问题时，所需要的代价是固定的。
一般这类问题的解题过程：（自己总结）
画出子问题图（类似于逆拓扑排序的图，子问题必须在问题前面完成）
用数学表达式构建出问题的最优解和子问题最优解之间的代数表达式
通常采用自底向上的方法进行递归地求解问题的解，自底下上的含义是从最小的子问题求起。
保存每一步求出的子问题的最优解
利用计算出的信息构造一个最优解
3、贪心算法：
基本原理：从初始状态出发，每步都经过贪心选择，最终得到问题的最优解。
含义： 将每一步都看成是当前最佳的选择，做到局部最优化，直到无法选择为止。寄希望于局部最优的选择能够导致全局最优解。
两个实例：最小生成树算法和单源最短路径算法，以及集合覆盖问题的贪心启发式算法。
prim算法：将集合A看成是一棵树，每次选择剩余的节点中与这棵树形成的边的权值最小的点加入到集合A中形成新的树，循坏调用该过程，知道所有的点都已经放入到集合A中。初始时随机选择一个节点放入到集合A中。
kruskal算法：在所有连接森林中两颗不同树的边里面，找到权重最小的边（u，v），并将其加入到集合A中，循环调用该过程，直到所有的点已经放入到集合A中
贪心选择：当进行选择时，我们直接作在当前问题看来是最优的选择，而不必考虑子问题的解。这与动态规划不同，动态规划当前问题依赖于较小的子问题。而贪心算法中做当前问题最优选择，这样每步之后只需要做一个子问题的解。
也必须满足最优子结构的性质，即一个问题的最优解包含其子问题的最优解。
那么，如何区分什么时候使用动态规划，什么时候使用贪心算法呢？
典型的两个问题，0-1背包和分数背包。两者都具有最优子结构性质，但是贪心算法只能用来求分数背包的问题，而不能用来求0-1背包的问题。即只有分数背包具有贪心选择性。
我得总结（不一定对）：具有贪心选择性的一类问题是：每次做选择时只有性能不同，而代价是一样的。那么这样每次的选择都是最好的，最终会得到最好的结果。
哈夫曼编码也使用贪心选择算法。每次选择待编码的字符都选择在剩余的字符中出现次数最多的
㈨ 刘汝佳的算法艺术与信息学竟赛13页1.2.2节贪心法例一：钓鱼！分析部分第一段话怎样理解
贪心法(Greedy algorithm)是一种在每一步选择中都采取在当前状态下最好/优的选择，从而希望导致结果是最好/优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市， 那这就是一种贪心算法。
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它每对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
贪心法可以解决一些最优性问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
贪心法解题特点
贪心法有一个共同的点就是在最优求解的过程中都采用一种局部最优策略，把问题范围和规模缩小最后把每一步的结果合并起来得到一个全局最优解。
贪心法解题的一般步骤
（1）从问题的某个初始解出发；
（2）采用循环语句，当可以向求解目标前进一部时，就根据局部最优策略，得到一个部分解，缩小问题的范围和规模；
（3）将所有部分解综合起来，得到问题最终解。
㈩ 哈夫曼编码的贪心算法所需的计算时间
哈夫曼编码的贪心算法所需的计算时间O(nlogn)。根据查询相关公开信息显示，O(nlogn)是一个程序的效率，表示如果有n个数，最多要进行多少次运算，如exhaustivesearch的时间就是o(n)，因为如果有n个数，最坏情况就要经过n次比较，而binarysearch就是o(logn).因为只要log2（2在下面）n的时间就可以。