第16章 贪心算法

16.1 活动选择问题

书上的伪代码：

#include <iostream>using namespace std;#define N 11//一个活动用一个结点表示struct node{int id;int start;int finish;}A[N+1];//递归贪心算法，在第i个活动执行结束之后的贪心策略，初始时i=0void Reccursive_Activity_Selector(int i, int n){//找到第一个开始时间在第i个活动结束之后的活动int m = i+1;while(m <= n && A[m].start < A[i].finish)m++;//若找到了if(m <= n){//将这个活动作为执行活动cout<<m<<' ';//递归第m个活动执行结束之后的贪心策略return Reccursive_Activity_Selector(m, n);}cout<<endl;return;}//迭代的贪心算法void Greedy_Activity_Selector(){//在第i个活动执行结束之后的贪心策略，初始时i=0int n = N, i = 0, m;for(m = 1; m <= n; m++){//找到第一个开始时间在第i个活动结束之后的活动if(A[m].start >= A[i].finish){//将这个活动作为执行活动cout<<A[m].id<<' ';//递归第m个活动执行结束之后的贪心策略i = m;}}cout<<endl;}/*0 0 //虚构活动a01 43 50 65 73 85 96 108 118 122 1312 14*/int main(){int i;//输入测试数据for(i = 0; i <= N; i++){A[i].id = i;cin>>A[i].start>>A[i].finish;}Reccursive_Activity_Selector(0, N);Greedy_Activity_Selector();return 0;}

练习

16.1-1

待解决

16.1-2

先对每个活动按照它们的开始时间从小到大排序。令初始时i=n+1，其结束时间无限大，每次选择"结束时间比第i个活动的开始时间早的“的最晚开始活动

#include <iostream>#include <algorithm>using namespace std;#define N 11//一个活动用一个结点表示struct node{int id;int start;int finish;}A[N+1];bool cmp(node a, node b){return a.start < b.start;}//16.1-2void Greedy_Activity_Selector2(){//先对每个活动按照它们的开始时间从小到大排序sort(A, A+N+1, cmp);int n = N, i = -1, m;for(m = n; m >= 1; m--){//找到最后一个“结束时间在第i个活动开始之前”的活动if(i == -1 || A[m].finish <= A[i].start){//将这个活动作为执行活动cout<<A[m].id<<' ';//递归第m个活动执行开始之前的贪心策略i = m;}}cout<<endl;}/*0 0 //虚构活动a01 43 50 65 73 85 96 108 118 122 1312 14*/int main(){int i;//输入测试数据for(i = 0; i <= N; i++){A[i].id = i;cin>>A[i].start>>A[i].finish;}Greedy_Activity_Selector2();return 0;}

16.1-3

见 算法导论-16.1-3#include <iostream>#include "Heap.h"using namespace std;#define N 6extern int length;int result[N+1];//哈夫曼树struct Huffman_Tree{node *root;Huffman_Tree():root(NULL){}};//哈夫曼编码void Huffman(unsigned int *A, Huffman_Tree *T){int n = N;while(n > 1){//生成一个新的结点node *z = new node;//选择堆顶元素作为其左结点z->left = (node *)Heap_Extract_Min(A);//选择堆顶元素作为其右结点z->right = (node *)Heap_Extract_Min(A);z->p = z->left->p + z->right->p;//将新结点插入堆中Min_Heap_Insert(A, (unsigned int)z);n--;}//剩下最后一个结点时，这个结点就是树的根结点T->root = (node *)Heap_Extract_Min(A);}//输出这棵树上每个字母的编码void PrintTree(node *t, int cnt){int i;//叶子结点if(t->data != -1){//输出其值及编码cout<<t->data<<' ';for(i = 0; i < cnt; i++)cout<<result[i];cout<<endl;return ;}//非叶子结点，对其孩子进行递归result[cnt] = 0;PrintTree(t->left, cnt+1);result[cnt] = 1;PrintTree(t->right, cnt+1);}/*f 5e 9c 12b 13d 16a 45*/int main(){unsigned int A[N+1] = {};//存储的是结点的地址length = N;int i;char c;double p;//构造N个结点for(i = 1; i <= N; i++){cin>>c>>p;node *z = new node(c, p);A[i] = (unsigned int)z;}//构造最小堆Build_Min_Heap(A);//构造哈夫曼树Huffman_Tree *T = new Huffman_Tree();Huffman(A, T);//输出编码结果PrintTree(T->root, 0);return 0;}

习题

16.3-2

能

16.3-6

#include <iostream>#include "Heap.h"//选择p最小的结点时要借助于堆来实现using namespace std;#define N 6extern int length;int result[N+1];//哈夫曼树struct Huffman_Tree{node *root;Huffman_Tree():root(NULL){}};//哈夫曼编码void Huffman(unsigned int *A, Huffman_Tree *T){int n = N;while(n > 1){//生成一个新的结点node *z = new node;if(n--){//选择堆顶元素作为其左结点z->left = (node *)Heap_Extract_Min(A);z->p = z->p + z->left->p;}if(n--){//选择堆顶元素作为其中间结点z->middle = (node *)Heap_Extract_Min(A);z->p = z->p + z->middle->p;}if(n--){//选择堆顶元素作为其右结点z->right = (node *)Heap_Extract_Min(A);z->p = z->p + z->right->p;}//将新结点插入堆中Min_Heap_Insert(A, (unsigned int)z);n++;}//剩下最后一个结点时，这个结点就是树的根结点T->root = (node *)Heap_Extract_Min(A);}//输出这棵树上每个字母的编码void PrintTree(node *t, int cnt){int i;//叶子结点if(t->data != -1){//输出其值及编码cout<<t->data<<' ';for(i = 0; i < cnt; i++)cout<<result[i];cout<<endl;return ;}//非叶子结点，对其孩子进行递归result[cnt] = 0;PrintTree(t->left, cnt+1);result[cnt] = 1;PrintTree(t->middle, cnt+1);if(t->right){result[cnt] = 2;PrintTree(t->right, cnt+1);}}/*f 5e 9c 12b 13d 16a 45*/int main(){unsigned int A[N+1] = {};//存储的是结点的地址length = N;int i;char c;double p;//构造N个结点for(i = 1; i <= N; i++){cin>>c>>p;node *z = new node(c, p);A[i] = (unsigned int)z;}//构造最小堆Build_Min_Heap(A);//构造哈夫曼树Huffman_Tree *T = new Huffman_Tree();Huffman(A, T);//输出编码结果PrintTree(T->root, 0);return 0;}

思考题：

16-1 找换硬币

a）每次都尽量选最大的、

c）1 4 5

d）找换i分钱的最少硬币数是ans[i]，ans[i] = max{ans[i-s[j]]+1}

#include <iostream>#include <algorithm>using namespace std;//用于排序bool cmp(int a, int b){return a < b;}int main(){int n, k, i, j;//输入数据cin>>n>>k;int s[100], ans[100];for(i = 0; i < k; i++)cin>>s[i];//对硬币从小到大排序sort(s, s + k, cmp);//找换i分钱的最少硬币数是ans[i]memset(ans, 0, sizeof(ans));//ans[i] = max{ans[i-s[j]]+1}for(i = 1; i <= n; i++){for(j = 0; s[j] <= i; j++){if(ans[i] == 0 || ans[i-s[j]]+1 < ans[i])ans[i] = ans[i-s[j]]+1;}}cout<<ans[n]<<endl;return 0;}

16-2 最小化平均结束时间的调度

a）每当一个任务执行完时，就选则剩下的任务中选择执行时间最短的任务执行

b）每当一个任务执行完时，就选则剩下的任务中选择剩余执行时间最短的任务执行，每当一个新的任务到来时，如果它的执行时间比当前任务的剩余执行时间要短，就抢占