贪婪算法
贪婪算法
在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择,贪心策略使用的前提是局部最优能导致全局最优。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
由于贪心时可能会用到优先队列,这里再回顾一下优先队列的创建方式:
priority_queue<int> q;//默认降序排列,即大值优先级高
//1. 引入<funcional>库实现升序
priority_queue<int, vector<int>, less<int>> q;//降序排列
priority_queue<int, vector<int>, greater<int>> q;//升序排列
//2. 自定义cmp结构体时,return xx<xx; 表示降序
struct cmp{
bool operator()(Node* &a, Node* &b)
{
return a->value > b->value;
}
};
priority_queue<Node*,vector<Node*>,cmp> que;
//3. 目标类中直接定义比较方式
class student{
...
friend bool operator < (const student &s1, const student &s2){
return s1.grade < s2.grade;//降序
}
}
priority_queue<student> que;
huffman树
核心就是每次贪婪选择最小的两棵子树(叶子)。
描述
给定一个字符串,求出该字符串的huffman编码的长度和。
思路
1. 用map统计各个字符个数
2. 将个数封装成Node类,放入优先队列中,升序排列。
3. 每次取头两个,加和后再放进优先队列,如果是叶子节点就放进一个vector中(可以通过判断是否有孩子实现)。
代码
#include <vector>
#include <string>
#include <iostream>
#include <functional>
#include <map>
#include <queue>
using namespace std;
class Node{
public:
int value;
Node *parent = NULL;
Node *left = NULL;
Node *right = NULL;
Node(int value=0):value(value){}
Node(const Node &n){
value = n.value;
parent = n.parent;
left = n.left;
right = n.right;
}
};
struct cmp{
bool operator()(Node* &a, Node* &b)
{
return a->value > b->value;
}
};
int main()
{
string str = "qqweweasq";
map<char, int> m;
for (int i = 0; i < str.size(); i++){
if (m.find(str[i]) == m.end())
m.insert(pair<char, int>(str[i], 1));
else
m[str[i]]++;
}
priority_queue<Node*,vector<Node*>,cmp> que;
for (auto &i : m)
que.push(new Node(i.second));
vector<Node*> vec;
Node *a,*b,*p;
while (que.size() != 1){
a = que.top();que.pop();
b = que.top(); que.pop();
p = new Node(a->value + b->value);
p->left = a; a->parent = p;
p->right = b; b->parent = p;
que.push(p);
if (a->left==NULL)
vec.push_back(a);
if (b->left==NULL)
vec.push_back(b);
}
int res = 0;
for (auto n : vec){
int tmp = 0;
Node *p = n;
while (p->parent != NULL){
tmp++;
p = p->parent;
}
res += tmp;
}
cout << endl<<res;
system("pause");
return 0;
}
队列里面放指向节点的指针,因为要保证每个节点在内存中的位置不变,否则拷贝来拷贝去容易出现如parent指针指向为空的情况。
可以看到,这里的节点指针都是手动new 内存的,虽然指针可能会释放掉(?),但是指针指向的内存不会自动释放。所以创建的所有节点有且只有一个,没有拷贝的情况。
最短路径算法 dijkstra
核心:每步贪婪选择最短边。
描述
https://vjudge.net/problem/ZOJ-1221
前19行里输入与第i行相邻的城市有n个,以及n个城市的编号,给出一个数m,再每给出两个城市的编号,求最短距离。
思路
其实就是简化版的最短路径算法,其中路径长度都为1(如果存在路径的话)。
代码
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#define MAX 1000000
using namespace std;
struct node{
int dis;
int index;
node(int index, int dis = 1) :dis(dis), index(index){}
friend bool operator<(const node &node1, const node &node2){
return node1.dis < node2.dis;
}
};
vector<vector<int>> vec;
priority_queue<node> que;
void dijkstra(int from, int to)
{
vector<int> last(21, -1);
vector<int> mdis(21, MAX);
vector<int> visited(21,0);
last[from] = from;
visited[from] = 1;
for (int i = 1; i <= 20; i++){
mdis[i] = vec[from][i];
if (i!=from&&mdis[i]!=MAX)
que.push(node(i));
}
while (!que.empty()){
node n = que.top();
que.pop();
visited[n.index] = 1;
for (int i = 1; i <= 20; i++){
if (!visited[i] && vec[n.index][i] != MAX){
que.push(node(i));
if (mdis[i]>mdis[n.index] + vec[n.index][i]){
mdis[i] = mdis[n.index] + vec[n.index][i];
last[i] = n.index;
}
}
}
}
cout << from << " to " << to << ": " << mdis[to] <<endl;
}
int main()
{
int num = 1;
int n, tmp;
while (cin>>n){
for (int i = 0; i <= 20; i++)
vec.push_back(vector<int>(21, MAX));
for (int i = 0; i < n; i++){//第一行单独操作,
vec[1][1] = 0;
cin >> tmp;
vec[1][tmp] = 1;
vec[tmp][1] = 1;
}
for (int i = 2; i <= 19; i++){
vec[i][i] = 0;
cin >> n;
for (int j = 0; j < n; j++){
cin >> tmp;
vec[i][tmp] = 1;
vec[tmp][i] = 1;
}
}
cin >> n;
cout << "Test Set#" << num++ << endl;
int from, to;
for (int i = 0; i < n; i++){
cin >> from >> to;
dijkstra(from, to);
}
}
system("pause");
return 0;
}
上一篇: 如何利用QQ群迅速找到准客户?
下一篇: 贪婪算法