简答题

考虑使用动态规划方法求解下列问题：
01背包数据如下表，求：能够放入背包的最有价值的物品集合。

如设：V（i，j）——前i个物品中能够装入承重量j的背包中的最大总价值。请将如下递推式填写完整：

自底向上：按行或列填写下表。

考虑在序列A[1..n]中找最大最小元素的问题。一个分治算法描述如下：如果n≤2就直接求解。否则，将序列等分成两个子序列A[1..n 2]和A[n 2+1..n]，分别找出这两子序列的最大最小元素x1，y1和x2，y2；然后据此求出A[1..n]的最大元素x=max{x1，x2}及最小元素y=min{y1，y2}。请给出该算法计算时间T（n）满足的递归方程，并解方程来确定算法的时间复杂度。假定n=2k（k为正整数）。 点击查看答案

考虑用哈夫曼算法来找字符a，b，c，d，e，f的最优编码。这些字符出现在文件中的频数之比为20：10：6：4：44：16。要求： （1）简述使用哈夫曼算法构造最优编码的基本步骤； （2）构造对应的哈夫曼树，并据此给出a，b，c，d，e，f的一种最优编码。 点击查看答案