期末复习——贪心算法

╰半橙微兮° 2022-06-02 02:46 205阅读 0赞

【1】活动安排问题  
设有n个活动的集合E=\{1,2,3,……..,n\},其中每个活动都要求使用同一资源，而在同一时间内只有一个活动使用这一资源。每个活动i都有一个要求使用该资源的起始时间 si 和结束时间 fi, 且si

//4d1 活动安排问题 贪心算法
    #include "stdafx.h"
    #include <iostream> 
    using namespace std; 
    
    template<class Type>
    void GreedySelector(int n, Type s[], Type f[], bool A[]);
    
    const int N = 11;
    
    int main()
    {
        //下标从1开始,存储活动开始时间
        int s[] = {
       0,1,3,0,5,3,5,6,8,8,2,12};
    
        //下标从1开始,存储活动结束时间
        int f[] = {
       0,4,5,6,7,8,9,10,11,12,13,14};
    
        bool A[N+1];
    
        cout<<"各活动的开始时间,结束时间分别为："<<endl;
        for(int i=1;i<=N;i++)
        {
            cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;
        }
        GreedySelector(N,s,f,A);
        cout<<"最大相容活动子集为："<<endl;
        for(int i=1;i<=N;i++)
        {
            if(A[i]){
                cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;
            }
        }
    
        return 0;
    }
    
    template<class Type>
    void GreedySelector(int n, Type s[], Type f[], bool A[])
    {
        A[1]=true;
        int j=1;//记录最近一次加入A中的活动
    
        for (int i=2;i<=n;i++)//依次检查活动i是否与当前已选择的活动相容
        {
            if (s[i]>=f[j])
            { 
                A[i]=true;
                j=i;
            }
            else
            {
                A[i]=false;
            }
        }
    }

【2】最优装载  
有一批装载箱要装上一艘承重量为c的轮船，其中每个集装箱 i 的重量为 w .最优装载问题求在装载体积不受限制的条件下，将尽可能多的集装箱装入轮船。  
问题描述:  
有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。  
编程任务： 对于给定的n个集装箱和轮船的载重量C，编程计算装入最多时的集装箱个数。  
输入:  
输入由多组测试数据组成。每组测试数据输入的第1行中有2个正整数n和C。正整数n是集装箱个数；正整数C是轮船的载重量。接下来的一行中有n个整数，分别表示n个集装箱的重量，它们之间用空格分隔。其中1<=n<=2000，所有正整数不超过231-1  
输出:  
对应每组输入，输出的每行是计算出的装入最多时的集装箱个数。  
样例输入:  
4 5  
3 5 2 1  
样例输出:  
2

#include <stdio.h>  
    int main()  
    {  
        int c,i,j,n,temp,sum,index;  
        int a[100];  
        while(scanf("%d %d",&n,&c),n,c)  
        {  
            for(i=0;i<n;i++)  
                scanf("%d",a+i);  
            for(i=0;i<n-1;i++)               //排序   
            {  
                for(j=i+1;j<n;j++)  
                {  
                    if(a[i]>a[j])  
                    {  
                        temp=a[i];  
                        a[i]=a[j];  
                        a[j]=temp;  
                    }  
                }  
            }  
    
            sum=0;  
            index=0;  
            for(i=0;i<n;i++)         //最小的装上   
            {  
                if(a[i]<c-sum)  
                {  
                    sum+=a[i];  
                    index++;  
                }  
            }  
            printf("%d\n",index);  
        }  
    
        return 0;  
    }

【3】哈夫曼编码  
二叉树中有一种特别的树——哈夫曼树（最优二叉树），其通过某种规则（权值）来构造出一哈夫曼二叉树，在这个二叉树中，只有叶子节点才是有效的数据节点（很重要），其他的非叶子节点是为了构造出哈夫曼而引入的！  
哈夫曼编码是一个通过哈夫曼树进行的一种编码，一般情况下，以字符：‘0’与‘1’表示。编码的实现过程很简单，只要实现哈夫曼树，通过遍历哈夫曼树，规定向左子树遍历一个节点编码为“0”，向右遍历一个节点编码为“1”，结束条件就是遍历到叶子节点！因为上面说过：哈夫曼树叶子节点才是有效数据节点！  
【4】多机调度问题  
设有n个独立的作业\{1,2,3,4,……..,n\}，由m台相同的机器进行加工处理，作业 i 所需处理的时间为 ti 。现在约定，任何一个作业都可以在任何一个机器上加工处理，但作业未完成前不允许中断，任何作业不能拆分成更小的子作业。  
多机调度问题给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。采用最长时间作业优先的贪心选择策略，当n<=m时，只要将机器 i 的\[0,ti\]时间区间分配给作业 i 即可。当n>m时，首先将n个作业依其所需的处理时间从小到大排序，然后依次顺序将作业分配给空闲的处理机。  
某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，任何作业在被处理时不能中断，也不能进行拆分处理。现厂长请你给他写一个程序：算出n个作业由m台机器加工处理的最短时间。

输入  
第一行T（1

#include<iostream>  
    #include<algorithm>  
    #include<string.h>  
    using namespace std;  
    int speed[10010];  
    int mintime[101];  
    bool cmp( const int &x, const int &y )  
    {  
        return x > y;  
    }  
    int main()  
    {  
        int t;  
        cin>>t;  
        while(t--)  
        {  
            int m, n;         
            memset(speed, 0, sizeof(speed));  
            memset(mintime, 0, sizeof(mintime));  
            cin>>n>>m;  
            for(int i = 0; i < n; ++i)  
            {  
                cin>>speed[i];  
            }  
            sort(speed, speed + n, cmp);  
            for(int i = 0; i < n; ++i) //同时满足n <= m和n > m  
            {  
                *min_element(mintime, mintime + m) += speed[i];  //当mac >= task时，复制 mac < task时，最小元素累加（贪心倒罗）  
            }   
            cout<<*max_element(mintime, mintime + m)<<endl; //最大的即为总时间  
        }  
        return 0;  
    }