《趣学算法》第二章 贪心算法源代码

标签：als   哈夫曼   大于等于   最小值   秘书   fine   ret   end   path   

贪心算法相关代码实现

以下代码搬运自《趣学算法》实战演练

1、加勒比海盗船——最优装载问题

#include 
#include 
const int N=1000005;
using namespace std;

double w[N]; //古董的重量数组
int main()
{
    double c;
    int n;
    cout>c>>n;
    cout>w[i]; //输入每个物品重量
    }
    sort(w,w+n); //按古董重量升序排序
    double tmp=0.0;
    int ans=0; // tmp为已装载到船上的古董重量，ans为已装载的古董个数
    for(int i=0;i>c>>n;
    cout>s[i].w; //输入每个古董重量,用空格隔开
    }
    sort(s,s+n,cmp);
    double tmp=0.0;
    int ans =0;  //ans记录已经装载的古董个数，tmp代表装载到船上的古董的重量
    for(int i=0;i

2、阿里巴巴与四十大盗——背包问题

//program 2-2
#include
#include
using namespace std;
const int M=1000005;
struct three{
    double w;//每个宝物的重量
    double v;//每个宝物的价值
    double p;//性价比
}s[M];
bool cmp(three a,three b)
{
    return a.p>b.p;//根据宝物的单位价值从大到小排序
}
int main()
{
    int n;//n 表示有n个宝物
    double m ;//m 表示毛驴的承载能力
    cout>n>>m;
    cout>s[i].w>>s[i].v;
        s[i].p=s[i].v/s[i].w;//每个宝物单位价值
    }
    sort(s,s+n,cmp);
    double sum=0.0;// sum 表示贪心记录运走宝物的价值之和
    for(int i=0;is[i].w )//如果宝物的重量小于毛驴剩下的承载能力
        {
            m-=s[i].w;
            sum+=s[i].v;
        }
        else//如果宝物的重量大于毛驴剩下的承载能力
        {
            sum+=m*s[i].p;//部分装入
            break;
        }
    }
    cout

3、高级钟点秘书——会议安排

//program 2-3
#include 
#include 
#include 
using namespace std;
struct Meet
{
    int beg;   //会议的开始时间
    int end;   //会议的结束时间
    int num;   //记录会议的编号
}meet[1000];   //会议的最大个数为1000

class setMeet{
  public:
    void init();
    void solve();
  private:
    int n,ans; // n:会议总数 ans: 最大的安排会议总数
};

//读入数据
void setMeet::init()
{
    int s,e;
    cout > n;
    int i;
    cout >s>>e;
        meet[i].beg=s;
        meet[i].end=e;
        meet[i].num=i+1;
    }
}

bool cmp(Meet x,Meet y)
{
    if (x.end == y.end)
        return x.beg > y.beg;
    return x.end =last)
        {            //如果会议i开始时间大于等于最后一个选中的会议的结束时间
           ans++;
           last = meet[i].end;
           cout 

4、一场说走就走的旅行——最短路径

//栈实现
#include 
#include
#include
using namespace std;
const int N=100; // 城市的个数可修改
const int INF=1e7; // 无穷大10000000
int map[N][N],dist[N],p[N],n,m;//n城市的个数，m为城市间路线的条数
bool flag[N]; //如果s[i]等于true，说明顶点i已经加入到集合S;否则顶点i属于集合V-S
void Dijkstra(int u)
{
   for(int i=1; i(dist[t]+map[t][j]))
             {
               dist[j]=dist[t]+map[t][j] ;
               p[j]=t ;
             }
       }
}
void findpath(int u)
{
  int x;
  stacks;
  cout> n;
        cout >m;
        cout > u >> v >> w;
            map[u][v] =min(map[u][v],w); //邻接矩阵储存，保留最小的距离
        }
        cout > st;
        Dijkstra(st);
        cout 

//队列实现
#include 
#include 
#include
#include
using namespace std;
const int N = 100; // 城市的个数可修改
const int INF = 1e7; // 无穷大
int map[N][N],dist[N],n,m;
int flag[N];
struct  Node{
    int u,step;
    Node(){};
    Node(int a,int sp){
        u=a;step=sp;
    }
    bool operator a.step;
    }
};
void Dijkstra(int st){
    priority_queue  Q;  // 优先队列优化
    Q.push(Node(st,0));
    memset(flag,0,sizeof(flag));//初始化flag数组为0
    for(int i=1;idist[t]+map[t][i])
                {   // 求距离当前点的每个点的最短距离,进行松弛操作
                    dist[i]=dist[t]+map[t][i];
                    Q.push(Node(i,dist[i]));// 把更新后的最短距离压入优先队列，注意：里面的元素有重复
                 }
            }
        }
    }
}
int main()
{
        int u,v,w,st;
        system("color 0d");//设置背景及字体颜色
        cout > n;
        cout >m;
        for(int i=1;i>u>>v>>w;
            map[u][v]=min(map[u][v],w); //邻接矩阵储存，保留最小的距离
        }
        cout>st;
        Dijkstra(st);
        cout "

5、神秘电报密码——哈夫曼编码

//program 2-5
#include
#include
#include
using namespace std;
#define MAXBIT    100
#define MAXVALUE  10000
#define MAXLEAF   30
#define MAXNODE   MAXLEAF*2 -1

typedef struct
{
    double weight;
    int parent;
    int lchild;
    int rchild;
    char value;
} HNodeType;        /* 结点结构体 */

typedef struct
{
    int bit[MAXBIT];
    int start;
} HCodeType;        /* 编码结构体 */
HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */
HCodeType HuffCode[MAXLEAF];/* 定义一个编码结构体数组*/
/* 构造哈夫曼树 */
void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n){
    /* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
       x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
    int i, j, x1, x2;
    double m1,m2;
    /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
    for (i=0; i>HuffNode[i].value>>HuffNode[i].weight;
    }
    /* 构造 Huffman 树 */
    for (i=0; i>n;
    HuffmanTree(HuffNode,n);  //构造哈夫曼树
    HuffmanCode(HuffCode,n);  // 哈夫曼树编码
    //输出已保存好的所有存在编码的哈夫曼编码
    for(i=0;i

6、沟通无限校园网——最小生成树

//program 2-7
#include 
#include 
using namespace std;
const int N = 100;
int nodeset[N];
int n, m;
struct Edge {
    int u;
    int v;
    int w;
}e[N*N];
bool comp(Edge x, Edge y) {
    return x.w > n >> m;
        Init(n);
        cout > e[i].u>> e[i].v >>e[i].w;
        sort(e, e+m, comp);
        int ans = Kruskal(n);
        cout 

//program 2-7-1
#include 
#include 
using namespace std;

const int N = 100;
int father[N];
int n, m;

struct Edge {
    int u;
    int v;
    int w;
}e[N*N];

bool comp(Edge x, Edge y) {
    return x.w  q)
        father[p] = q;//小的赋值给大的集合号
    else
        father[q] = p;
    return 1;
}

int Kruskal(int n)
{
    int ans = 0;
    for(int i=0;i> n >> m;
        Init(n);
        cout >e[i].u>>e[i].v>>e[i].w;
        sort(e, e+m, comp);
        int ans = Kruskal(n);
        cout 

《趣学算法》第二章 贪心算法源代码

标签：als   哈夫曼   大于等于   最小值   秘书   fine   ret   end   path   

原文地址：https://www.cnblogs.com/self-confidence/p/13603491.html