贪心算法-Huffman树
1. 哈并果子问题的概述及案例
https://www.acwing.com/problem/content/150/
上图为本问题的案例。
实际上，本题就是霍夫曼树的应用。关于霍夫曼树的定义，这里就不再赘述。
根据上图，实际上这道题就是在询问：将所有的果子堆进行合并，构造成一颗树之后(最终合并为一堆之后)，如何使得总消耗(带权路径之和)最小？很明显，哈夫曼树就可以保证带权路径之和最小。我们只需要将这些果子堆构成一颗哈夫曼树即可。
2. 合并果子问题的步骤
1. 每次从容器中选择两个最小权值的堆，进行合并。将合并之后的堆放回到容器中。
2. 重复上述过程，直到容器中只剩一堆为止。
很明显，上述的过程实际上就是在构造哈夫曼树的过程。
3. 合并果子问题的证明
这道题的证明，本质上就是对哈夫曼树进行证明。
哈夫曼树的特点就是：每次选取最小的两个点进行合并，这样所得到的一定是最优解。因此，最小的两个点一定深度最深。
1. 现在我们证明：最小的两个点，深度一定最深且可以互为兄弟。我们在这里采用反证法：最小的两个点深度不是最深。假设，a，f点是最小的两个点。a点位于最后一层(n)，f点位于n-1层。（具体树的形状见上图）。当我们将f点与b点进行替换之后，权值一定降低。因此，当最小的两个点深度不是最深时，一定不是最优解。因此，最小的两个点，深度一定最深且可以互为兄弟。
2. 当我们将n个点进行合并时，我们一定会将权值最小的两个点进行合并。此时还剩n-1个点。我们将从n个点合并成为1个点的某个具体方案记为f(n)。为了求出最优方案，显然每一个f(n)在第一步的时候，都需要将两个权值最小的点进行合并。因此：f(n) = f(n-1) + a + b;(其中，a和b是n个点中权值最小的两个点)。由于，每一个f(n)都会有一个固定常数a+b。因此在求出最佳方案时，我们可以将每一个f(n)后面的a+b去掉。若如此做，并不会影响最佳方案的求解。因此，我们将f(n)的计算变成了f(n-1)的计算。
3. 对于n-1个点，我们也可以采用上述的方式进行计算。这样就由：f(n-1)的计算转换成了f(n-2)的计算。
4. 一直进行下去，当从2个点合并成为1个点之后，所得到的解就是全局最优解。
4. 合并果子问题的代码
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int n;
priority_queue<int,vector<int>,greater<int>> heap;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int a;
scanf("%d",&a);
heap.push(a);
}
int res = 0;
while(heap.size() > 1){
int a = heap.top();
heap.pop();
int b = heap.top();
heap.pop();
res += (a+b);
heap.push(a+b);
}
printf("%d",res);
return 0;
}
作者：gao79138
链接：https://www.acwing.com/
来源：本博客中的截图、代码模板及题目地址均来自于Acwing。其余内容均为作者原创。
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。