算法设计与分析——贪心算法部分例题
·
4.5哈夫曼树编码
测试数据：
输入：
5
a 12
b 40
c 15
d 8
e 25
11010011102
输出：
a 1111
b 0
c 110
d 1110
e 10
cebd
参考代码：
#include <iostream>
#include <bits/stdc++.h>
#include <queue>
#include <stack>
#include <string>
#include <math.h>
#define inf 0x3f3f3f3f
using namespace std;
//贪心算法例题：哈夫曼树建立及编码过程：
struct node //哈夫曼树结点
{
char ch;
int weight;
int lchild,rchild,parent;
}huffman[101];
struct node2 //用来存储每个字符的编码；
{
char bits[101];
char ch;
int start;
}code[101],cd;
void bulid_tree(int f[],char ch1[],int n) //建立哈夫曼树
{
int m = 2*n - 1;
for(int i=0; i<m; i++) //初始化操作
{
huffman[i].lchild = -1;
huffman[i].rchild = -1;
huffman[i].parent = -1;
huffman[i].weight = 0;
}
for(int i=0; i<n; i++) //生成n棵树即n个叶子节点
{
huffman[i].ch = ch1[i];
huffman[i].weight = f[i];
}
for(int i=n; i<m; i++) // 进行（n-1)次合并
{
int x ,y; //找到此次需要合并的两棵树
int min_x=inf, min_y = inf;
for(int j=0; j<i; j++)
{
if(huffman[j].parent == -1)
{
if(huffman[j].weight < min_x) //寻找最小值
{
min_y = min_x;
min_x = huffman[j].weight ;
y = x;
x = j;
}
else // 寻找次小值
{
if(huffman[j].weight < min_y)
{
min_y = huffman[j].weight ;
y = j;
}
}
}
}
//将（x,y)合并：
huffman[x].parent = i;
huffman[y].parent = i;
huffman[i].weight = min_x+min_y;
huffman[i].lchild = x;
huffman[i].rchild = y;
}
}
void huffman_code(int n)//哈夫曼树转为哈夫曼编码
{
for(int i=0; i<n; i++) //从底部向上
{
cd.start = n;
cd.ch = huffman[i].ch;
int p = huffman[i].parent;
int c = i;
while(p != 0)
{
cd.start--;
if(huffman[p].lchild == c)
{
cd.bits[cd.start] = '0';
}
else
{
cd.bits[cd.start] = '1';
}
c = p;
p = huffman[c].parent;
}
code[i] = cd;
}
}
void decode(int n)//依次读入字符串编码并进行解码
{
char b[1001];
gets(b);
int j=0;
int i = 2*n - 2;
while(b[j] != '2')
{
if(b[j] == '0')
{
i = huffman[i].lchild;
}
if(b[j] == '1')
{
i = huffman[i].rchild;
}
if(huffman[i].lchild == -1 && huffman[i].rchild == -1)
{
cout<<huffman[i].ch;
i = 2*n - 2;
}
j++;
}
cout<<endl;
}
int main()
{
int n;
cin>>n;
char ch1[100];
int f[101];
getchar();
for(int i=0; i<n; i++)
{
cin>>ch1[i]>>f[i];
getchar();
}
bulid_tree(f,ch1,n);
huffman_code(n);
for(int i=0; i<n; i++)
{
cout<<" "<<code[i].ch<<" ";
for(int j=code[i].start+1;j<=n; j++)
{
cout<<code[i].bits[j];
}
cout<<endl;
}
decode(n);
cout<<endl;
return 0;
}
4.6 最小生成树
prim算法
输入：
6
10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
输出：
1 3 1
3 6 4
6 4 2
3 2 5
2 5 3
参考代码：
#include <iostream>
#include <bits/stdc++.h>
#include <queue>
#include <stack>
#include <string>
#include <math.h>
#define inf 0x3f3f3f3f
using namespace std;
//贪心算法例题：最小生成树 ——prime 算法
int c[101][101];
int vis[101];
void prim(int n)
{
int close_[101];
int low_[101];
int s[101];
for(int i=2; i<=n; i++)
{
close_[i] = 1;
low_[i] = c[1][i];
s[i] = 0;
}
s[1] = 1;
for(int i=1; i<n; i++)
{
int minn = inf;
int j = 1;
for(int k=2; k<=n; k++)
{
if(!s[k] && minn > low_[k])
{
minn = low_[k];
j = k;
}
}
s[j] = 1;
cout<<close_[j]<<" "<<j<<" "<<minn<<endl;
for(int k=2; k<=n; k++)
{
if(!s[k] && low_[k] > c[j][k])
{
low_[k] = c[j][k];
close_[k] = j;
}
}
}
}
int main()
{
int n;
cin>>n;
int m;
cin>>m;
memset(c,inf,sizeof(c));
while(m--)
{
int x,y,p;
cin>>x>>y>>p;
c[x][y] = p;
c[y][x] = p;
}
prim(n);
return 0;
}
kruskal 算法：
输入：
6
10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
输出：
1 3 1
4 6 2
2 5 3
3 6 4
2 3 5
参考代码：
#include <iostream>
#include <bits/stdc++.h>
#include <queue>
#include <stack>
#include <string>
#include <math.h>
#define inf 0x3f3f3f3f
using namespace std;
//贪心算法例题：最小生成树 ——kruskal算法
struct node
{
int x;
int y;
int c;
/*bool operator <(const node &p) const{
return c < p.c;
}
*/
}mp[101];
bool cmp(node p1,node p2)
{
return p1.c<p2.c;
}
int f[1001];
int get_f(int x)
{
return f[x] == x ? x: get_f(f[x]);
}
int union_(int x, int y)
{
int x1 = get_f(x);
int y1 = get_f(y);
if(x1 != y1)
{
f[y1] = x1;
return 1;
}
return 0;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1; i<=m; i++)
{
cin>>mp[i].x>>mp[i].y>>mp[i].c;
}
sort(mp+1, mp+1+m,cmp);
for(int i=1; i<=n; i++)
{
f[i] = i;
}
int sum = 0;
for(int i=1; i<=m; i++)
{
int x = mp[i].x, y = mp[i].y;
if(union_(x,y))
{
sum ++;
cout<<x<<" "<<y<<" "<<mp[i].c<<endl;
}
if(sum == n-1)
{
break;
}
}
}
4.7 多机调度问题
输入：
7 3
2 14 4 16 6 5 3
输出：
16
17
17
17
参考代码：
#include <iostream>
#include <bits/stdc++.h>
#include <queue>
#include <stack>
#include <string>
#include <math.h>
#define inf 0x3f3f3f3f
using namespace std;
//贪心算法例题：多机调度问题
int t[101];
bool cmp(int x,int y)
{
return x > y;
}
void greedy_(int n,int m)
{
int ty[101];
for(int i=1; i<=m; i++)
{
ty[i] = t[i];
}
int minn = inf;
int j = m;
for(int i=m+1; i<=n; i++)
{
ty[j] += t[i];
minn = ty[j];
for(int k = m; k>=1; k--)
{
if(minn > ty[k])
{
minn = ty[k];
j = k;
}
}
}
int maxn = 0;
for(int i=1; i<=m; i++)
{
cout<<ty[i]<<endl;
if(maxn < ty[i])
{
maxn = ty[i];
}
}
cout<<maxn<<endl;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>t[i];
}
sort(t+1,t+1+n,cmp);
if(n <= m)
{
cout<<t[1]<<endl;
}
greedy_(n,m);
return 0;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
1
0- 0
已为社区贡献2条内容
所有评论(0)